If my C memory can come back to me I remember a spiffy trick was to unroll loops. Right now you are doing a foreach, try something like this.

sub Which($)
  {
   my $Filename=shift;
   my @Arr = ( split /\:/,$ENV{PATH} )
   for(my $i = 0; $i <= #$Arr; $i += 2)
   {
    return "$Arr[$i]/$Filename\n" if ( -e "$Arr[$i]/$Filename" );
    return "$Arr[$i+1]/$Filename\n" if ( -e "$Arr[$i+1]/$Filename" );
   };
  }
[download]

Sorry about that previous post, big ol RTFM on my part. This code's sorta ugly but you get the picture I'm sure, have it check 3 or 4 at a time and you'd be amazed how much faster it will run.