It's hard to know exactly, but I think your problem is here:

foreach $pair (@pairs) 
{
($key,$value) = split (/=/, $pair);
  chomp ($value);
 
   foreach $name (@names) 
   {
    $name =~s /\s$key/$value/ig;
    @newrecords = (@newrecords,"$name");
   }
}
[download]

This code recompiles the regular expression on every execution. Perl doesn't know that it only changes on every pass through the outer loop. I would replace it with something like this:

foreach $pair (@pairs) {
  ($key,$value) = split (/=/, $pair);
  chomp $value;

  # compile pattern to match $key with qr//
  my $match = qr/\b\Q$key\E\b/;

  # serach and replace names and push onto @newrecords
  foreach (@names) {
    s/$match/$value/gi;
    push @newrecords, $_;
  }
}
[download]

This version also incorporates the eariler good advice concerning \b, \Q, \E and push().

If that doesn't help you, consider slowing down and analyzing the performance of your program. Use Devel::DProf and/or Benchmark to get a better idea of how your code performs and where the time is being spent. Performance problems are very hard to solve by guessing.

-sam