It's a tradeoff. As the OP noted, if you increase the range of squares you're checking, precomputing gets slower (and it's time you don't count in your benchmark). Stick another 0 on MAX_NUMBER and run your bench again (change the first arg for cmpthese to -10), and you might get something like I did:

         Rate Regexp  Index   Sqrt
Regexp 3.82/s     --   -88%   -98%
Index  32.4/s   748%     --   -81%
Sqrt    167/s  4281%   417%     --
[download]

One relatively easy optimization that I didn't do is to limit the length to what can actually be matched:

sub m_sqrt {
    my $total_length;
    my %seen;
    my $max_length = length($MAX_NUMBER * $MAX_NUMBER);
    for my $start (0..length $string) {
        next if substr($string, $start, 1) eq '0';
        my $this_max = length($string)-$start;
        $this_max = $max_length if $max_length < $this_max;
        for my $length (1..$this_max) {
            my $test = substr($string, $start, $length);
            my $sqrt = sqrt($test);
            if (!$seen{$test}++ and $sqrt == int $sqrt
                    and $sqrt >= $MIN_NUMBER and $sqrt <= $MAX_NUMBER)
+ {
                $total_length += $length;
            }
        }
    }
    return ($total_length);
}
[download]

Now the bench gives me

         Rate Regexp  Index   Sqrt
Regexp 3.64/s     --   -88%   -99%
Index  31.2/s   758%     --   -94%
Sqrt    497/s 13542%  1489%     --
[download]