Ah, shame! That destroys the symmetry I was exploiting and so requires two lots of not quite identical code :(

sub interleave {
    my( $a, $b ) = qw[ a b ];
    my( $as, $bs ) = @_;
    return $a x $as . $b x $bs unless $as >1 and $bs;

    if( $as > $bs ) {
        ++$bs;
        my $aPerB = int( $as / $bs );
        my $aRem = $as - $bs * $aPerB;
        my @as = ( $a x $aPerB ) x $bs;
        my $n = 0;
        $as[ $n ] .= $a, $as[ - ++$n ] .= $a, $aRem -= 2 while $aRem >
+ 1;
        $as[ @as / 2 ] .= $a if $aRem > 0;
        return join $b, @as;
    }
    else {
        --$as;
        my $bPerA = int( $bs / $as );
        my $bRem = $bs - $as * $bPerA;
        my @bs = ( $b x $bPerA ) x $as;
        my $n = 0;
        $bs[ $n ] .= $b, $bs[ - ++$n ] .= $b, $bRem -= 2 while $bRem >
+ 1;
        $bs[ @bs / 2 ] .= $b if $bRem > 0;
        return $a . join( $a, @bs ) . $a;
    }
}
__END__
C:\test>624887 -S=1 -N=50
 4a  5b: abbababba
 4a  7b: abbabbbabba

-----------

 4a 13b: abbbbabbbbbabbbba
 4a 14b: abbbbbabbbbabbbbba
 4a 15b: abbbbbabbbbbabbbbba
 4a 16b: abbbbbabbbbbbabbbbba
 4a 17b: abbbbbbabbbbbabbbbbba
 4a 18b: abbbbbbabbbbbbabbbbbba
 4a 19b: abbbbbbabbbbbbbabbbbbba

-----------

13a  4b: aaabaabaaabaabaaa
14a  4b: aaabaaabaabaaabaaa
15a  4b: aaabaaabaaabaaabaaa
16a  4b: aaabaaabaaaabaaabaaa
17a  4b: aaaabaaabaaabaaabaaaa
18a  4b: aaaabaaabaaaabaaabaaaa
19a  4b: aaaabaaaabaaabaaaabaaaa

-----------
[download]