You can mock out the functions that are legacy (disclaimer: I'm the author of Mock::Sub. There are several other similar distributions. Unfortunately, it doesn't look like I included a SEE ALSO section in this cut, but searching meta for "mock" should list a few).

Code untested. Mock::Sub can also return values, or perform side effects. Peruse the docs.

use warnings;
use strict;

use Mock::Sub;
use Test::More;

my $mock = Mock::Sub->new;

my $complicated_function 
  = $mock->mock('Old::Codebase::complicated_function');

{ 
    my $new_obj = New::Codebase->new;

    $new_obj->do_something_with_old_code();

    is (
        $complicated_function->called,
        1,
        "legacy method called ok"
    );

    is (
        $complicated_function->called_count,
        3,
        "legacy method called proper num times"
    );

    my @called_with = $complicated_function->called_with;

    is (
        $called_with[0],
        'param',
        "legacy method called with proper param"
    );

    $complicated_function->reset;
}

done_testing();
[download]