In Polish, Sunday is „niedziela”, and Monday is also „poniedziałek”, so it actually makes more sense than in Russian :) I suspect “niedziela” («неделя») was the original, proto-Slavic word for the day of the week, as some variations of it are used for I think all Slavic languages except Russian, who at some point decided to rename it to celebrate Resurrection.
Not-Doing can be a false alias: the week is nedelya and ponedelnik may thus mean "one going with the week*, i.e. starting it.
Altough I'm not sure since the sibling proto-slavic explanation makes much sense. Fun fact: slavic languages split off in medieval times when the calendar and the week were already thorougly taken care of.
In other Slavic languages it's mostly some form of ty + djen' (Polish tydzien Croatian tjedan Czech týden Belarusian тыдзень Ukrainian тиждень). But see Bulgarian (седмица seven-thing (fem.)).
I suspect (without evidence) that, in Russian, it's referring to Sundays as a way of reckoning weeks.
week:Sunday :: year:summer :: month::moon. Cf. "When I was but 10 summers old", "Many moons ago", etc.
That would fit with the use of the archaic word for Sunday as well.
It looks like Polish is similar except that Sunday is "Not-Doing"