|Sir Paul rocks it (source)|
The word itself dates to the mid-15th century from Anglo-French molette, which derives from Old French mulet. Mulet comes from Middle Latin muletus, which derives from Latin mulettus from mullus ("red mullet"), a borrowing from Greek myllos. Myllos is a marine fish and the word is related to melos ("black"). All this, however, is only distantly related (maybe) to the fine hair style we all know and love. This is the etymology for mullet, meaning "edible, spiny-finned fish."
Mullet, meaning "hairstyle short on top and long in back" is not attested until 1994, though the style itself is clearly much older. It may come from mullet-head ("stupid, dull person"), but it certainly owes its popularity to the Beastie Boys, who first sang about it in their song "Mullet Head."