There are free scripts. Just be careful of spam etc. I ran one and had some interesting chats with my hosting company.
The one who develops should integrate it for you actually, besides there us usually only a single db table required to fuel such application. And there wont be any maintenance cost as far I know. Cost effective one you can buy with support: http://www.scriptbaba.com/demos/shorturl/ regards
Here's a free URL shortener to get going. http://www.scripteen.com/scripts/scripteen-free-url-shortener.html The running costs are low but be sure to maintain it.
The concept is trivial. When someone asks your site to shorten a URL, you create a unique, short string of characters. Store it, and the original URL in your database. When someone goes to your site with a short URL as an arg, look up the original URL and do a redirect [header("'Location: $real_url.')";]
So may of these sites around now - is it worth it? Especialy when cloaking affililiate links - they can get quite funny about it.
I was just thinking about this same thing. My quick idea would be to use Google’s URL Builder and then run that tracking url through your preferred url shortener.