This question seems to be pretty complicated and is asking a lot of things, so I'm going to break this down piece by piece.
How did the Sage of Six Paths obtain his Rinnegan?
Well, we really don't know whether he was born with it or obtained it after birth. What's important to know is that he was the first one that had it.
The stages/evolution of an Uchiha's eyes
Regular -> Sharingan (1->2->3 Tomoe) -> Mangekyou Sharingan -> Eternal MS -> Rinnegan
You are right about the progression, however you are mistaken when you ask
Now if the same logic was to be applied to the Sage of the Six Paths, then whose Mangekyo Sharingan did he take for his own?
The Sage of Six Paths did not have the Mangekyou Sharingan nor did he take the Mangekyou Sharingan from someone. He had the strongest and final form of the eye : Rinnegan.
When the Sage of Six Paths had two sons, his powers were split between them. One was Senju and inherited the Sage of Six Path's body strength. The other son was Uchiha and received the Sage of Six Path's ocular powers.
Keep in mind that both sons only received a fraction of what the Sage of Six Paths had. This is why all Uchiha always bore the Sharingan, which is a younger eye form for an Uchiha and has a fraction of the power of the Rinnegan.
Thus when a person wants to awake the Rinnegan, the requirements are both body and eye. An example of this is Uchiha Madara with the Sharingan and acquiring Senju Hashirama's DNA. With both DNA from Uchiha and Senju, he can finally become a Sage of the Six Paths and obtain the Rinnegan. And even while using the Rinnegan, Uchiha Madara is still able to use Mangekyou techniques like Susanoo, which confirms that Rinnegan is the final evolutionary state of the eyes.