I've not tried it, but how about overriding &CORE::GLOBAL::require? From there, you could use caller() to get information about how modules use each other.

Update: OK, now I've tried it:

use strict;
use warnings;

BEGIN {
    *CORE::GLOBAL::require = sub {
        my ($mod) = @_;

        my $caller = caller;
        warn "$caller uses $mod.\n";

        CORE::require($mod) unless $mod =~ /^5/;
    };
}

use CGI;
[download]

It's kind of quick and ugly, but seems to work.