You could read in the whole file and regex on that, but I'm assuming that's not something you want to do. You could read in chunks and look for the separator that way, but what if the separator crosses the chunk barrier? For instance, if you're matching on Separator \d+ and the barrier splits it into Separator 2|3 instead of Separator 23. That's no good. Lastly, if your file is in multiple lines, this is fairly easy using a line-by-line technique:

use strict;
use warnings;

my ($data, @records);

open (FH, 'data.txt') || die;
while (<FH>) {
    $data .= $_;
    push @records, $1
        while $data =~ s/(.*?)Separator \d+//s;
}
push @records, $data;

use Data::Dumper;
print Dumper(\@records);
[download]

Data:

Record A Separator 9 Record B
Separator 10 Record C Separator 11
Record D
[download]

Output:

$VAR1 = [
          'Record A ',
          ' Record B
',
          ' Record C ',
          '
Record D'
        ];
[download]