Here's a not-quite-as-simple version that doesn't use a hash at all, and as little additional memory as possible. It exploits both the fact that one array is a proper subset of the other, and that the items appear in the same order in both arrays.

If the latter is not the case you'd have to sort it, which kinda defeats the memory advantage.

use strict;
use warnings;

my @p = ( 1,1,1,1,1,2,2,2,3,3,4,5,6);
my @q = ( 1,2,3,4,5,6 );

my ($px, $qx) = (0, 0);

my @diff;
while (1) {
    if ($qx >= @q){
        push @diff, @p[$px .. @p-1];
        last;
    } elsif ( $p[$px] == $q[$qx] ) {
        $px++;
        $qx++;
    } else {
        push @diff, $p[$px++];
    }
}

print "p: @p\n";
print "q: @q\n";
print "d: @diff\n";
[download]

Update: that code can be simplified a bit:

while ($qx < @q) {
    if ( $p[$px] == $q[$qx] ) {
        $px++;
        $qx++;
    } else {
        push @diff, $p[$px++];
    }
}
push @diff, @p[$px .. @p-1];
[download]