When Pac-Man dies, his body gradually deflates into a wedge type shape. I believe Pac-Man can do this at will, and, when aroused, forms himself into a wedge, and inserts himself into Ms. Pac-Man's only available cavity. At this point, he implants his seed into her, extracts himself, and continues on.

That or he uses binary fission or some other sort of cellular division. (Hey, that rhymes.)