Cape elk, large South African antelope, 1786, from Dutch eland "elk," probably from a Baltic source akin to Lithuanian elnias "deer," from PIE *el- (2) "red, brown" (see elk), cognate with first element in Greek Elaphebolion, name of the ninth month of the Attic year (corresponding to late March-early April), literally "deer-hunting (month)." Borrowed earlier in English as ellan (1610s, via French), ellend (from the German form of the word).
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.