While the advice above on refactoring is certainly excellent, and probably the best in the long run, you may also consider using an infrustructure like Apache's mod_perl. Sometimes, the porting of a system to mod_perl can be faster than refactoring all those modules.

The advantage you gain is that mod_perl applications compile once and remain running, so your compile time imports will only hurt you once. Of course, depending on how the application is constructed, mod_perl porting might actually be more work than refactoring your modules. Still, it's something to consider.

Regarding the refactor of the modules, I must say I really do feel sorry for you, as this is a ton of work. As a first step, follow the advice above on converting function calls to use the full namespace. Do that first, and the next steps are easier. Maybe this isn't the best approach, but it's what I did the last time I ran into this issue:

1. Convert all functions to full namespace, and all 'use' to 'require' (except for core Perl and CPAN modules, which you won't need anyhow).
2. Use your favorite diagramming system (I was forced into UML, which worked fine) to analyze each module and figure out its internal and external dependencies.
3. Get the system as is into version control.
4. Create a stub module for each subroutine in each module; for example, My::BigModule::function1() will become My::Module::Function1::function1() (note the change in case). It's easier to recombine modules than to split them further, so you might as well split as far as you can up-front.
5. One subroutine at a time, copy to the new module space and update your code to reflect the new namespace (search and replace works just fine for this). Test after you move each subroutine and make note of any that aren't used by anything. Also, be sure to update a copy of your dependency diagram.
6. Figure out which subroutines are always (or frequently) loaded together, and combine them.
7. Figure out which subroutines fit conceptually together and move them in your namespace as you see fit.

There are caveats: sometimes two subs will need to be packed together right away, with some data sturcture or other. This is why the dependency diagram is useful. In general, I found it helpful to start by splitting as much as possible: recombining modules is so much easier than splitting, and doing all the splitting up-front lets you lower your stress for the recombination stage.

Again, this may not be the best approach. It worked reasonably well for me, though; and it scales to teams, to some extent.