A record of which subs are actually being called ...

This sounds like a job for Devel::NYTProf or another of its ilk. Other monks than I will be better able to advise on the proper module and its employment.

... recording runs of a large legacy codebase - before and after making changes to it - as an aid to writing tests- which don't exist for this codebase. A record of ... which arguments & return values, is a good starting place showing what's in use = a starting place showing what to test.

This seems a bit bass-ackwards to me. The critical starting point for testing code is understanding the code (update: and its specification). This will be a huge task for a large, unfamiliar codebase. Writing tests for such a codebase will be an even hugerer task because you have to understand all the boundary cases of the invocation of each function. (Much of the time and effort of such a project may be spent cursing the name of the original coder who paid no attention to testing.)

And here's another problem: How do you know that the application is running properly right now? Do you have a way to evaluate an application run that tells you its output is "correct," or are you just depending on the fact that the program didn't blow up or your company go out of business to assure you that, well, everything's probably OK? Generating a huge database of input arguments/return values for each subroutine may be useless or worse if it captures and enshrines unrecognized incorrect behavior.

Refactoring a large application in the absence of a thorough test suite is a big job, and you're quite right to think that the first task is to create such a test suite. Unfortunately, there are no easy answers, and in particular, a database of assumed normal operation for each subroutine can be no more than an adjunct to a deep understanding of the application. Good luck.

Update: Looking back over this post, it just seems like a very verbose way of saying "You're gonna need a bigger boat!" and perhaps isn't very helpful in consequence, which I regret. (But I still wish you luck!)