QUESTION: The Gemara explains that the source for the obligation of Milah for a convert is the Milah the Jewish people performed when they left Mitzrayim.
Where, though, does the Torah mention that the Jewish people performed Milah when they left Mitzrayim in order to become Gerim? The only mention of Milah at the time of the Exodus is the Milah the Jewish people performed in order to be permitted to eat the Korban Pesach (Kerisus 9a), which was a specific commandment unrelated to becoming Jewish. (RAMBAN)
ANSWER: The RAMBAN and RASHBA explain that the Milah the Jewish people performed in Mitzrayim was not merely to permit them to eat the Korban Pesach. Moshe Rabeinu told them to perform Milah in order to accept the Mitzvos upon themselves and to be "Nichnas Tachas Kanfei ha'Shechinah" -- to become the nation of Hash-m. That is what the Mechilta (Shemos 12:6) means when it says that at the time of the Exodus the Jews lacked the merit of Mitzvos, and therefore Hash-m gave them two Mitzvos to perform -- Milah and the Korban Pesach (Mechilta Shemos 12:6). Hash-m gave these Mitzvos to the Jewish people in order to make them His chosen nation.
However, not every man in Mitzrayim needed to perform Milah in order to eat the Korban Pesach. Although most of the people had forsaken the Mitzvah of Milah until the night of the Exodus, the tribe of Levi always observed the Mitzvah of Milah (Devarim 33:9) as the RAMBAM explains (Hilchos Isurei Bi'ah 13:2). Accordingly, the men of the tribe of Levi did not need to perform Milah when they left Mitzrayim. When did they perform a Milah for the sake of conversion? The Milah they performed earlier was the fulfillment of the ordinary Mitzvah of Milah that was given to Avraham Avinu. It was not done for the sake of becoming Jewish.
(a) The RAMBAN and RASHBA suggest that the men of Levi performed "Hatafas Dam Bris" -- they let some blood from the place of their Milah for the purpose of conversion. The Gemara understands that every man who left Mitzrayim performed some form of Milah, either actual circumcision or "Hatafas Dam Bris."
(b) The RAMBAN suggests further that perhaps the men of Levi did not need Milah again because their original Milah was done to fulfill the Mitzvah of Hash-m. (The Ramban later compares the men of Levi to the women who converted with Tevilah alone.)
The Ramban apparently maintains that a man who already performed the Mitzvah of Milah is comparable to a man who physically is unable to perform Milah. A man who was born deformed and cannot perform Milah still can become a Ger without Milah (as Tosfos says on 46b, DH d'Rebbi Yosi). Similarly, if a man already performed the Mitzvah of Milah, it is not possible for him to perform Milah again for the sake of Gerus. The Milah of Gerus is not a new Mitzvah per se; rather, the Mitzvah is to perform an act of Milah for the sake of Gerus. If he already performed the Mitzvah of Milah, he cannot do it again for the sake of Gerus. Since it is impossible for him to perform Milah for the sake of Gerus, the lack of Milah for Gerus does not prevent him from becoming a Ger.
TOSFOS in Kerisus (9a, DH d'Kesiv) offers a similar answer but with a different logic. Tosfos suggests that even those who performed Milah because of the Mitzvah given to Avraham did so for the sake of Gerus and to accept upon themselves the yoke of Mitzvos. Avraham's Mitzvah was not just to perform Milah, but to do so in order to become a Jew.
(c) TOSFOS (46b, DH d'Rebbi Yosi, and Shabbos 135a, DH Lo Nechleku) quotes RABEINU CHANANEL who rules that even today a circumcised Nochri who comes to convert does not need "Hatafas Dam Bris" in order to become a Ger. He maintains that although the Nochri's Milah was a medical procedure devoid of any spiritual relevance, he is exempt from the requirement of Milah since he physically cannot do Milah again for the sake of Gerus. While other Rishonim maintain that for such a Nochri "Hatafas Dam Bris" must be done in place of Milah, Rabeinu Chananel disagrees. He maintains that "Hatafas Dam Bris" is done only for a child born with a Milah; since he was born that way, there is a different form of Milah for him -- "Hatafas Dam Bris." For one who was born normal, however, the only valid form of Milah is the removal of the Orlah, and one who had his Orlah removed already cannot have another Milah. (See Insights to Shabbos 135:2.) This approach explains why the tribe of Levi did not need a new Milah for Gerus.
(Although this seems to be the opinion of Rabeinu Chananel according to the way Tosfos quotes his words, Rabeinu Chananel may intend to say something else entirely. Rabeinu Chananel writes that because there is no "Hatafas Dam Bris" for a convert, a Nochri who is already circumcised cannot become a convert at all! (See Rabeinu Chananel to Shabbos 135b, where a few words seem to be missing in the version printed in the Vilna Shas, and see the words of Rabeinu Chananel as cited by the RAMBAN, TUR YD 268, and other Rishonim.) Rabeinu Chananel enigmatically adds that although his conversion does not entitle him to acceptance as a Jew, children born to him afterwards are Jews! None of the Rishonim concur with Rabeinu Chananel in this respect.)