• Reformat/reflow to your liking. Preferably with Perl::Tidy, so the new layout is both documented and reproducible.
• Do not rewrite function-based code to OO-based code just because it is more modern. There may be (very) good reasons other than modernizing the code, but simply because you think OO is more modern or because you like OO is a very bad reason for such a conversion. To me that sounds like implementing threads in a program that doesn't gain anything by that.
• Add comments! Everywhere that you needed time to investigate, add comments.
• Start writing tests based on the docs and based on any fix you make.
• Replace local option parsing functions with Getopt::Long and write a good usage function.
• Create a two-sided TODO list. On the left "Have to change", on the right "would love to change". Postpone the right until everything works and you have spare time.
• Use a good VCS, like git and commit often with very clear commit messages.

A good rule of thumb for the "often" part of local committing is:
you've changed something and managed to get it to compile again -> commit!

"managed to get it to compile again" o.O? I'm going to assume you mean "have added thorough tests for the changed code and confirmed they all pass".
Me

I'm sure you'll find lots of discussions when you search for "legacy code".

Just two points:

App::Ack is like a better grep, and very valuable for finding where specific variables/functions/methods are used.

The more change, the more you break. If lots of work has been put into the old code base, it might be worth to change only the bits you need to change, instead of introducing massive-scale changes like porting all classes to Moose. (Of course that doesn't apply if you have to touch nearly all code anyway).

1. Identify change points
2. Find an inflection point
3. Cover the inflection point
  a. Break external dependencies
  b. Break internal dependencies
  c. Write tests
4. Make changes
5. Refactor the covered code.

Cut the blue wire!

Update: Sorry, I meant the red one.

I am in short supply of time.

If this is really, really true: don't try rewrite anything excepting the exact requirements you've got. Just try to understand what's there, extend it, and blend in with it.

As you go, after you've had time to understand the code better and what exactly it does, write tests. Rewriting without taking the time hit to write tests is false economy. Every 10 minutes you save not writing tests can come back and cost you an hour, or maybe even a couple of days, debugging and maybe much more in lost customers when bugs make it to production.

Or... a complete rewrite. If you have to redo most of it, it will likely be easier than retooling the original in situ. But, again, without a full functional spec or test suite or both, this will bite you hard. Sometimes 10K lines of code can be compressed to a few hundred with judicious application of the stars of the CPAN but that assumes you know exactly what you're doing and what the code is doing. Good luck and come back often with technical questions if you've got them. Many monks here can pull apart seeming Gordian knots easily.

Take off and nuke the site from orbit. It's the only way to be sure.

You cannot completely modify to new requirements and/or"modernize" it AND do it fast AND do it good, all at the same time.

Depending on how extensive your modifications will be to answer the new requirements, a total "modern" rewrite may actually be easier.

The fact that there are no tests available is a major problem.

In any case, the first thing to do is write these tests. Without tests you will be actually navigating at night in dense fogs through unchartered waters and with no radar! Without tests you cannot be certain that what you wrote is not broken.

I am in the wretched thick of just such a project right now.   The code is horrid.   One key practice for me is to make one code change at a time and to do it in a (git ...) separate branch.   This makes parallel sets of changes which are more-or-less tagged to why I made them.   I am also keeping a “running log” – a diary – of everything that I am doing, and I’m making the entire team do the same thing.

The “Dealing Effectively” book, mentioned earlier, is one that of course I have looked at, but, having looked at it, didn’t buy.   I felt that it might be “the cat’s meow” if you happened to have stumbled upon a bunch of object-oriented code that just wasn’t quite up to snuff, but it had very little practical advice to offer with regard to the large mass of existing (true “legacy”) code that wasn’t built that way.

Be wary of “change for the sake of change,” or what a former colleague of mine once called, “making it ‘–er.’”   You need to familiarize yourself with the code very thoroughly, and then consider what is the least intrusive set of changes that must be made in order to satisfy the new requirement.   Sometimes that isn’t the right approach:   sometimes the thing is so near dead that you have to grab the ol’ defrib paddles and shout, “Clear!”   But just remember that, if you blast the thing apart, you still have to put it all back together and send it running down the road at sixty miles an hour ...