Based on the info you provided, I suggest starting with some interface testing. At this point, your work/reward ratio will be quite high because you are already experiencing "fix one, break two" and some regression.

Most of the suggestions so far have focussed on standard Perl testing, which is generally unit testing. I'll offer a different option. You mention CGI scripts, so you could build tests to excercise the interface. Take notes on how you have found previous bugs through the browser. Then you can look into automating that sequence using WWW::Mechanize and Test::WWW:Mechanize.

We did this for a large amount of existing web code because in addition to not having tests, much of our older code wasn't very 'testable.' Creating new unit tests would have involved a lot of refactoring because the code wasn't modular. Building tests of the interface was much easier and effective.

Then, moving forward, consider all of the advice above. Each time you add code or fix a bug, make the code very modular and testable and write tests for it. That way you will be in good shape moving forward. If you take this approach when you fix bugs, your 'buggy' code will start to have much better coverage and you'll experience many fewer bugs.