I’ve been wondering this for a while now. The second half of Alexander the Great’s name looks very much like the genitive singular of ανήρ re-interpreted as a second-declension nominative singular. Is this indeed the derivation, and if so, is such re-interpretation common in compounds involving ανήρ?
The Abridged Greek Lexicon has:
ἀλέξ-ανδρος, ον, (ἀλέξω, ἀνήρ) defending man.
II. the usual name of Paris in the Iliad.
Funny name for Paris.
Yes it is.
We have, for instance, “Evander” (Εὔανδρος) and Lysander (Λύσανδρος) plus others I can’t think of right now 
Menander, Cleander, Alcander, Cassander, Leander…
… and my personal favorite, Philander. 
Just check the oxford index of Greek personal names, you’ll find a million
The phenomenon of -andros being used in compounds is clearly common, but I disagree with your explanation of it. It is the anhr form of the noun that is the irregular one and it is normal for compound words to be formed on the root rather than nominative. For example compounds of pas are pant- and there are many other examples. The root of anhr is andr, so those are the consonants used in the compound. -os is just a noun ending that happens to look like the genitive of the original noun.