This version fairly picks (exactly) 50% from 40e6 in 8 seconds*(10MB); 50% from 100e6 in 22 seconds*(25MB); 50% from 1e9 in under 4 minutes*(1/2GB). It can handle all the way up to 25e9 using <3GB in under 2 hours*:

(*)plus the time taken to read the file.

#! perl -slw
use strict;
use Math::Random::MT qw[ rand ];
use constant FOUR_GB => 2**32;

$|++;
our $N ||= 40e6;
our $K ||= $N / 2;

## A bit vector big enough to hold any number in the range
my $vector = chr(0) x (( $N  + 7 ) / 8);

## Populate it with random bit values
## As we are after 50% this will get us very close very quickly
substr $vector, $_* 4, 4, pack( 'V', rand( FOUR_GB ) )
    for 0 .. ( length( $vector ) / 4 ) -1;

## How many did we actually pick?
my $nBits = unpack '%32b*', $vector;

## Now (fairly) adjust up or down accordingly
while( $nBits++ < $K ) {
    ## pick bit to set
    my $r = int( rand $N );

    ## If it is already set discount it
    $nBits -= vec( $vector, $r, 1 );

    ## and set it anyway
    vec( $vector, $r, 1 )=1;
}

while( $nBits-1 > $K ) {
    ## pick bit to clear
    my $r = int( rand $N );

    ## If it is set discount it
    $nBits -= vec( $vector, $r, 1 );

    ## and clear it anyway
    vec( $vector, $r, 1 ) = 0;
}

## Read the file line by line
$\=undef;
while( <> ) {
    ## print it if it was picked
    print if vec( $vector, $., 1 );
}
[download]

It can also handle ratios other than 50%, but will start getting far less efficient as you move further away from 50% (up or down).