Without looking into it any deeper, a simple approach is to stop recalculating the "cleaned" version of a string for each comparison. For that, you will need to move the cleaning out of the function compare and up in to the loop calling compare:

for my $string1 (@strings_left) {
    my $string1_clean = clean( $string1 );
    for my $string2 (@strings_right) {
        if( compare($string1_clean, clean( $string2 )) {
            ...
        }
    };
};
[download]

If you have some more memory, you can Memoize the cleanup of the string. This would speed up cleaning up strings a bit more.

But maybe you can save more comparison time by first sorting all your strings into buckets based on the first (few) characters of the string. There is no way that a string starting with "A" will be equal to a string starting with "B". That could cut down on the total number of comparisons made.