This idea is untested, but may meet your requirements:

CGI::Carp overrides warn and die to get its messages into the error log. Try perldoc -m CGI::Carp for more details.

$main::SIG{__WARN__}=\&CGI::Carp::warn;
$main::SIG{__DIE__}=\&CGI::Carp::die;
sub warn {
#...
}
sub die {
#...
}
[download]

You could customize your access logging as described in chapter 16 of the mod_perl cookbook, so that a unique key gets recorded in the access log for each request (a timestamp using Time::HiRes might be sufficient, if not, you can find some discussion about generating unique ids by going to the mod_perl mailing list archives and searching for the phrase"unique id").

You can store this key into $r->pnotes, then override warn and die like CGI::Carp does and have those subroutines warn/die with the key added to the message. It looks like you could use CGI::Carp almost as-is, if you just rewrite the 'stamp' subroutine to pull the key out of $r->pnotes and possibly the IP address out of $r as well, then use all the rest of the CGI::Carp code.

Then you would have a key in both the error log and the access log that you could match by.