late Old English elch, from Old Norse elgr or from an alteration of Old English elh, eolh (perhaps via French scribes), or possibly from Middle High German elch (OED's suggestion), all from Proto-Germanic *elkh- (source also of Old High German elaho). The modern word "is not the normal phonetic representative" of the Old English one [OED].
The Germanic words are related to the general word for "deer" in Balto-Slavic (such as Russian losu, Czech los; also see eland), from PIE *olki-, perhaps with reference to the reddish color from root *el- (2) "red, brown" (in animal and tree names); compare Sanskrit harina- "deer," from hari- "reddish-brown." Greek alke and Latin alces probably are Germanic loan-words. Applied to similar-looking but unrelated animals in North America. Benevolent and Protective Order of Elks founded N.Y.C. 1868, originally a society of actors and writers.