Something like this?

my $x = rand(65536);
foreach (@lines) {
   open(my $fh_out, '>', sprintf('prefix%04X.txt', $x)) or die;
   print $fh_out $_;
   $x = ($x + 1) % 65536;
}
[download]

I'm not sure how useful it is to start at a random number if you only increment afterwards.

Update: Ah! you're not refering to the variable named $RANDOM that exists in some shells. You're refering to some randomly named variable.

my $x = 0;
foreach (@lines) {
   open(my $fh_out, '>', sprintf('prefix.%04d.txt', $x++)) or die;
   print $fh_out $_;
}
[download]

Or if you are reading from file handle,

while (<$fh_in>) {
   open(my $fh, '>', sprintf('prefix.%04d.txt', $.)) or die;
   print $fh_out $_;
}
[download]