I admit my solution is not mathematically pure, and is similar to Grandfather's first suggestion. Rather than storing up all those numbers, my approach is to note that we have to choose half of the lines. So do we use a line or not? 50/50 chance. That could easily give a shortfall, but I have a hack for that:

use warnings;
use strict;

my $limit    = 40_000_000;
my $how_many = $limit/2;
my $hits = 0;

open (my $handle, 'rand_sorted.txt') or die "Unable to open rand_sorte
+d.txt: $!";

# Using a C style loop to avoid a large temp list (Grandfather)

for (my $i = 0; $i < $limit && $hits < $how_many; $i++) 
{  
    my $record = <$handle>;
    
    if (rand(2) > 1 || ($limit-$i) <= $hits ) {
        $hits++;
        
        # Do what you must to the record
        print "$i: $record\n";
    }
}

close ($handle);
[download]