"Hau ab!" is the imperative of abhauen, which has the colloquial meaning (among others) of to escape quickly.
The Duden derives it from hauen, which means to beat and is said to refer to beating a horse with the spurs on your boots. Grimm's dictionary still mentions the meaning to hurry, to run for hauen and gives the same reasoning:
13) hauen endlich für eilen, streben, laufen. diese bedeutung hat wol ihren ausgang von dem einhauen der sporen in des rosses weichen
Together with the prefix ab- (off, away) you get to run away, to get off quickly.
But note that this old meaning of hauen is no longer present, and Grimm's doesn't say abhauen to mean to escape. If they didn't miss it, the verb must have derived this meaning after this part of the dictionary was written, but before hauen lost its meaning of to hurry.
This gives room to a second theory: according to the book Westjiddisches Wörterbuch, the verb abhauen might derive from abbauen, which is Rotwelsch for to escape, to flee and has Yiddish origins. It is further said to have a Hebrew root that means to come.
A Rotwelsch, i.e. thieve's argot, origin might also have contributed to the derogative touch of abhauen, which in turn can also explain (to some degree at least) why "Hau ab" sounds rather rude, as you mention in your question.