Doing without the array slice may improve it:

{
  use integer;
  for my $i1 (0 .. $#LongListOfIntegers) {
    for my $i2 ($i1+1 .. $#LongListOfIntegers) {
      my $v = $LongListOfIntegers[$i1];
      my $w = $LongListOfIntegers[$i2];

      unless ($v & $w & ~1) {
        $MatchedIntegers{$v}{$w} = 1;
        $MatchedIntegers{$w}{$v} = 1;
      }
    }
  }
}
[download]