Do it client-side. Don't break the web.
1. you need to block the click event until you get a response from your analytics endpoint. Google suggests doing this by adding a 100ms delay: http://support.google.com/googleanalytics/bin/answer.py?hl=e...
2. you might get holes in your data for a number of reasons: the user has JS turned off; 100ms isn't long enough for the request to go through; or the user might click off before your script can attach itself to the onclick event.
You definitely don't want to get yourself in a situation where you go down and all outbound links stop working, but if you can fail gracefully, replacing the link makes a lot more sense.