Running Makefile.PL creates a Makefile that is executed by make. What make does is an automated, but complex process. To get some idea of what's going on behind the curtain, read the module's Makefile, while referring to ExtUtils::MakeMaker as a study guide. In the end, your module gets installed somewhere, and man pages get installed, along with the possibility of some other stuff getting installed here and there, depending on the distribution. My best guess in your case is that while you've managed to delete the module code, you may have left the man pages, and that's what is still showing up.

But I don't know for sure. What I do know is that uninstalling by hand something that an automated tool created can be messy and prone to missing something. This is why AnonymousMonk's suggestion for a tool from CPAN that can automate the process is a good one. However, it does require that you install another CPAN module. Perl's core utilities don't include a module uninstaller.