The thing below (with arbitrary, fabricated arrays) takes approximately 1m15s on my old 600 MHz machine. How does it compare to your running time? If I'm not mistaken, this scans the first and second arrays once, running a count on every valid thing it finds. Anyone with suggestions on how to do better, feel free to comment.

#!/usr/bin/perl

use strict;
use warnings;

my (@array1, @array2);
my %seen;

# Fabricate some array
use List::Util qw(shuffle);
@array2 = shuffle (0..1000000);
@array1 = @array2[0..950000];


# Scan our first array
foreach my $key (@array1) {
        $seen{$key} = 0;
}

# Search our second array
foreach my $key (@array2) {
        # Check if valid key    Yes, count it   No, warn
        defined($seen{$key}) ?  $seen{$key}++   : warn qq{Key '$key' f
+ound, but not searching for it.\n};
}

# Determine the item count
foreach my $item (keys %seen) {
        my $count = $seen{$item};

        if ($count == 1) {
                # Only once, as intended
        }
        elsif ($count == 0) {
                # Missing, report
                print qq{Item '$item' not found in search array.\n};
        }
        else {
                # Multiple items, report
                print qq{Item '$item' found multiple ($count) times in
+ search array.\n};
        }
}
[download]