That's hard to say without actually seeing your code.

You will have to identify the functions that are used from both places and move these into a third file which is loaded by both of the other files.

I haven't encountered problems when doing that, but maybe you have two functions that invoke each other:

sub foo {
    if( $_[0] ) {
        bar( $_[0] -1 )
    };
};

sub bar {
    if( $_[0] ) {
        foo( $_[0] -1 )
    };
};
[download]

These functions cannot be easily split in two, but depending on their functionality, maybe there is a way to rewrite them so that the common functionality can be removed.

after reading Corion's post, I want to ask: If you draw a dependency graph "who calls whom", did you perhaps try to divide them not into branches or layers, but grouping them otherwise?