This does the same thing as your Clone method but takes 1/3rd the time (for 10x10 matrices), just by not doing the completely redundant second map:

sub Clone2 {
    my $self = shift @_;
    my $matrix = $self->Matrix;
    return Matrix->new(
        "Matrix" => [ map{ [ @$_ ] } @$matrix ]
    );
}
[download]

If your matrices are very small (3x5 or 4x4 or less), then it might be worth breaking some OO taboos to gain a little more. This also does the same thing, but avoids a couple of method calls per invocation:

sub Clone3{
    my $self = shift;
    bless { "Matrix" => [ 
        map{ [ @$_ ] } @{ $self->{Matrix} } ] 
    }, 'Matrix';
}
[download]

But in the end, if a call that takes 3 milliseconds (your original for a 100x100 matrix) takes 80% of your time, then you should really start questioning why it is necessary to Clone something 35 million times? It seems to me that using a better algorithm is likely to produce far greater savings.