Using the eval subroutines was a step too far. Whilst much better than eval for every line, the additional subroutine call still has a substantial impact.

Going back to hardcoded trs, and you get the picture we were both expecting:

C:\test\ACA>..\junk71 -N=4
            (warning: too few iterations for a reliable count)
    Rate     b     a
b 1.45/s    --  -98%
a 85.1/s 5751%    --

C:\test\ACA>..\junk71 -N=10
            (warning: too few iterations for a reliable count)
    Rate     b     a
b 2.94/s    --  -97%
a 91.7/s 3025%    --

C:\test\ACA>..\junk71 -N=20
            (warning: too few iterations for a reliable count)
    Rate     b     a
b 4.55/s    --  -96%
a  116/s 2453%    --

C:\test\ACA>..\junk71 -N=50
            (warning: too few iterations for a reliable count)
    Rate     b     a
b 6.67/s    --  -95%
a  133/s 1900%    --

C:\test\ACA>..\junk71 -N=100
    Rate     b     a
b 7.93/s    --  -95%
a  149/s 1776%    --
[download]

Updated benchmark code:

#! perl -slw
use strict;
use Benchmark qw[ cmpthese ];

sub makeTR{
    eval "sub{ \$_[ 0 ] =~ tr[$_[0]][$_[1]] }";
}

our $N //= 10; die "$N must be even and positive" if $N &1 or $N < 2;
our $tr1 = makeTR( '!', "\n" );
our $tr2 = makeTR( "\n", '!' );
our $flag = 0;
our $s = '1234!' x 55e3;

cmpthese $N, {
    a => q[
        if( $flag ) {
            my( $p, $c ) = ( 0, 50e3 );
            1 while --$c and $p = index $s, "\n", $p;
            $s =~ tr[\n][!]; #$tr2->( substr $s, 0, $p );
            $flag ^= 1;
        }
        else {
            my( $p, $c ) = ( 0, 50e3 );
            1 while --$c and $p = index $s, "!", $p;
            $s =~ tr[!][\n]; #$tr1->( substr $s, 0, $p );
            $flag ^= 1;
        }
    ],
    b => q[
        if( $flag ) {
            $s =~ s/\n(??{ ( $myregexp::count++ < 50000 ) ? '' : '(?!)
+' })/!/g;
            $flag ^= 1;
        }
        else {
            $s =~ s/!(??{ ( $myregexp::count++ < 50000 ) ? '' : '(?!)'
+ })/\n/g;
            $flag ^= 1;
        }
    ],
};
[download]