In Russian the word for week is "nedelya", so "ponedelnik" does seem to naturally tie into that. But the word for Sunday in Russian is "voskresenie" (literally means resurrection). Notice this! Every religious word used in non-religious context is suspicious!
If we examine Bulgarian, the week is called "sedmica" (sedm == seven). And Sunday is called "nedelya" (I perceive it as "ne delya" === "no work").
Thus, in Bulgarian the word ponedelnik becomes like "the day after Sunday", rather than "the day starting every week".
Now going back to the Sunday resurrection theme, it's obviously of religious origins, so I dare assume that it may have replaced something that was already there (like nedelya). And then I imagine the people still wanted to keep the word around, so they started using it to mean "week" instead of "Sunday".
If so, then it would make sense that ponedelnik just means "post Sunday".
[The above is just a pet theory I haven't spent any time on, so I'm not guaranteeing its legitimacy]
Matthew 28:1 (NIV): “After the Sabbath, at dawn on the first day of the week, Mary Magdalene and the other Mary went to look at the tomb.”
Mark 16:1–2 (NIV): “When the Sabbath was over, Mary Magdalene, Mary the mother of James, and Salome bought spices so that they might go to anoint Jesus’ body. 2 Very early on the first day of the week, just after sunrise, they were on their way to the tomb…”
Luke 24:1 (NIV): “On the first day of the week, very early in the morning, the women took the spices they had prepared and went to the tomb.”
John 20:1 (NIV): “Early on the first day of the week, while it was still dark, Mary Magdalene went to the tomb…”
I believe that they resurrected the practice of considering Sunday as the first day of the week, based on the Old Testament tradition. Just like New Earth Creationism is in fact a relatively recent phenomenon driven by a renewed interest in literal interpretations of the Bible, that had long since been superseded in Catholic scholarship.
There are also several patristic writings that conceptualise Sunday as the eighth day of creation, i.e. the resurrection perfecting and completing creation (this also suggests that literal seven day creation wasn’t taken that… er… literally back in the day).
Monday = Segunda (second) = понедельник (start of the week)
Tuesday = Terça (third) = вторник (second)
Wednesday = Quarta (fourth) = среда (middle)
Thursday = Quinta (fifth) = Четверг (fourth)
Friday = Sexta (sixth) = пятница (fifth)
So I guess Russians have no doubt as to when the week starts.