Old English elles "in another manner, other, otherwise, besides, different," from Proto-Germanic *aljaz (source also of Gothic aljis "other," Old High German eli-lenti, Old English el-lende, both meaning "in a foreign land;" see also Alsace), an adverbial genitive of the neuter of PIE root *al- "beyond" (source also of Greek allos "other," Latin alius). As a quasi-adjective, synonymous with other, from 1660s; the nuances of usage are often arbitrary.
Productive of a number of handy compounds that somehow never got traction or have been suffered to fall from use: elsehow (1660s) "somehow or other;" elsewards (adv.), 1882, "somewhere else;" Old English elsewhat (pron.) "something else, anything else;" elsewhen (adv.), early 15c., "at another time; elsewhence (c. 1600); elsewho (1540s). Among the survivors are elsewhere, elsewise. Menacing or else, with omitted but implied threat, is from 1833.