While I agree that if you're going to break code into pieces it should be in response to some requirement of the code itself, I sympathise with the too-much-$@%! problem. Perhaps you could try:

a different text editor
This is a navigation problem, not a structure problem. Use an editor with better navigation features: syntax colouring, code folding, jump-to-method, position markers and good search tools will all help.

more POD
I find that well (and consistently) documented code is much easier to get around, especially if it has become unfamiliar. Consider spreading the docs throughout the module, rather than storing them at the end, and adopt a consistent structure to give easy visual cues when hunting for the right line.

question your premises
Why does it have to occupy a single namespace? That suggests a lot of globals or $package::variables, which will very likely have to be rooted out later for one reason or another. Refactor the requirement away.

seek help
Do you really need 4000 lines of code? Sifting carefully through CPAN could cut it down considerably and make it more readable too. Except I'm sure you did that already. And if all else fails:

use mixin;
mixins will let you separate code along whatever lines you like while preserving a single namespace. Schwern's adamantly lower-case module is very easy to use:

Package My::Enormous::Package;
use mixin 'My::Filingorsomething';

Package My::Filingorsomething
use mixin::with 'My::Enormous::Package';
[download]

Hope there's something useful in there. Please excuse if labouring obvious.