Find an algorithm you like for comparing edit-distance of two strings, and then just loop until it crosses a threshold or you run out of string.

use Text::WagnerFischer "distance";
use List::Util 'min';

my $a="abbaba";
my $b="ababbba";
my $limit= 3;

my $n= 0;
my $max= min(length $a, length $b);
++$n while $n < $max
        && distance(substr($a,-$n-1), substr($b,0,$n+1)) < $limit;

if ($n) {
  printf "'%s' matches '%s' with edit distance %d",
    substr($a,-$n), substr($b,0,$n),
    distance(substr($a,-$n), substr($b,0,$n))
}
[download]

To parallelize for extremely long matches, you could have N threads step $n += N.

Edit: sorry, I skimmed the second half of your question. For batches of 10 million pairs of smallish strings, I think you want to use C or C++. If you have a need to integrate it with Perl code, you can use Inline::C, or just IPC::Run to run a pool of C++ workers which you could then pipe data into and collect the responses. Note that edit distances are a harder problem than your example code can solve, since sometimes having solved it for N characters, adding 1 character could have an optimal edit distance by a completely different set of changes to the string. But, Wagner-Fischer is O(N^2) each time you run it, so maybe you can look for a new variation that calculates "sideways" for each new character rather than starting from scratch each time.

Edit Again: as anonymous points out, a better edit distance might come after a worse edit distance, so actually you would need to iterate over the whole range of substrings.