late Old English seldum, alteration of seldan "seldom, rarely," from Proto-Germanic *selda- "strange, rare" (source also of Old Norse sjaldan, Old Frisian selden, Dutch zelden, Old High German seltan, German selten), perhaps ultimately from the base of self (q.v.).
The form shifted on analogy of adverbial dative plurals in -um (such as whilom "at one time," from while). The same development also created litlum from little, miclum from mickle. Also compare random, ransom. German seltsam "strange, odd," Dutch zeldzaam are related, but with the second element conformed to their versions of -some.
Seldom-times is from mid-15c. (Old English had seldhwanne "seldwhen"). Seldom-seen is from mid-15c. (Old English had seldsiene, "seld-seen"). Some compounds using the old form survived through Middle English, such as selcouth"rarely or little-known, unusual, strange, wonderful," from Old English selcuð, seld-cuð, from seldan + cuð (see couth). Old English seldan had comparative seldor, superlative seldost; in early Middle English, as seldan changed form and lost its connection with these, selde was formed as a positive. Shakespeare uses seld-shown.