Just thought I'd share what I've found to be the most efficient path to finish this achievement and get the new merc. You can do this with any level char as long as they can use flying mounts (I've done it on a lvl 35). This ends with you right next to the tent where you can hire him.
I've just run it a couple more times and I'd recommend reversing the order of 3 & 4. Also, know that you might have to fly fairly low to get the update at the Warship Docks.
Yup... my running mate has about the same pattern - ran one of my toons through it the other night in about three minutes.