This!

Oh, and Skimmable Code (pdf)

It's a big PITA, but figure out what one giant function takes as inputs (included those absorbed through global osmosis), and what it excretes through returns and global manipulations. Figure out its side effects (opening of filehandles, etc). Then write regression tests for the function.

Next, follow Schwern's skimmable code techniques to break the big functions into smaller testable units, while writing unit tests to verify the functionality of these smaller units. Throughout the process, keep running the original regression tests.

Finally you'll be left with something that you can look at and understand how to fix. Most likely the fixes won't involve removing my $self = shift; -- that's just a red herring. The elephant in the corner is the humongous functions that probably don't strictly adhere to simple parameter passing.