I was confused by your textual description of the binary format as well as your code.

In general when processing binary files, avoid regex. Your friends should be: substr,ord,unpack and pack.
Reading a 500K binary file into a single var using binmode should be fine.
Below is a simple example, use unpack for multi-byte substrings. You can account for the difference between Intel byte order and Motorola byte order.

The relatively low level functions that I mentioned will "run like a rocket".

#!/usr/bin/perl
use strict;
use warnings;


my $f = "31FCFFFFFFFFFFFE5817300618262527262123216E5D5346172D620000C00
+000000000000000262F2D2D2D2E2D00008000000150591200A832C001D02625222289
+3360808026187CFF";
$f = pack("H*",$f);

# substr EXPR,OFFSET,LENGTH,REPLACEMENT

print "Number of bytes: ", length $f, "\n";
printf "record Len? : %x  hex \n",ord(substr($f,0,1));
print  "record Len? : ", ord(substr($f,0,1))," decimal \n";
print  "not right first byte, ASCII '1':", substr($f,0,1),"\n"; ##ASCI
+I "1";

__END__
Prints:
Number of bytes: 73
record Len? : 31  hex 
record Len? : 49 decimal 
not right first byte, ASCII '1':1
[download]

I would be thinking of a subroutine that you call like:

my $next_byte_index = process_record (\$data, $start_byte_index);
[download]

passing a reference to the data instead of the data itself will speed things up quite a bit.
To incorporate this into a loop, you will have to consider the "end conditions", when the loop ends and the difference between the length in bytes vs the "off by one" index number.