Here's one way to do it. Does not require much memory, and should be fairly fast. Not tested on 1MB files. :)

#!perl
use strict;

## Files to be loaded:
my @files = qw(file1.txt file2.txt file3.txt);

## New file to create:
my $newfoo = "Bigfile.txt";

my ($file, $number, %phone, %serial, %change);

{
local $/='';
for $file (@files) {
  open(FOO, "$file") or die "Could not open $file: $!\n";
  while(<FOO>) {
    ## Check for duplicate phone number
    /^Phone (.*)/m or die "No phone for record $.\n";
    $phone{$1}++ and $change{"$file$."}=-1 and next;

    ## If phone number cool, check the serial number:
    /^SERIAL NUMBER (\d+)/ or die "Bad serial number for record $.\n";
    ## Make sure it is unique, if not, add one
    if ($serial{$1}++) {
      $number=$1;
      1 while $serial{++$number};
      $serial{$number}++;
      $change{"$file$."}=$number;
    }
}
close(FOO);
} ## go to next file in the list

## Loop through them all again, this time for keeps :)
open(NEWFOO, ">$newfoo") or die "Could not create $newfoo: $!\n";
for $file (@files) {
  open(FOO, "$file") or die "Could not open $file: $!\n";
  while(<FOO>) {
    if ($change{"$file$."}) {
      $change{"$file$."}==-1 and next;
      s/^SERIAL NUMBER (\d+)/SERIAL NUMBER $change{"$file$."}/;
    }
    print NEWFOO $_;
  }
}
close(NEWFOO);
} ## end generic loop
[download]