From Middle High German ēmāles, ē māles (“formerly”), from ē (“before”) + genitive of māl (“time, occurrence”). Morphologically ehe + Mal + -s.
ehemals