I'd usurp Roy Johnson's lookup tables, but use two strings and substr rather than an @AoA.

A quick test on a 124MB file takes around a minute, with no great difference whether using 4096 byte or larger reads.

#! perl -slw
use strict;

our $SIZE ||= 4096;

my( $oddLU, $evenLU ) = ('') x 2;

for my $i ( 0 .. 0xffff ) {
    my( $oddByte, $evenByte ) = ('') x 2;
    my $word = pack 'n', $i;
    vec( ${  $_ &1 ? \$evenByte : \$oddByte }, $_>>1, 1 ) =
        vec( $word, $_, 1 ) for 0 .. 15;
    $oddLU .= $oddByte;
    $evenLU .= $evenByte;
}

open my $inFH, '<:raw:perlio', $ARGV[ 0 ] or die $!;
open my $oddFH, '>:raw:perlio', 'odd.bin' or die $!;
open my $evenFH, '>:raw:perlio', 'even.bin' or die $!;

local $/ = \$SIZE;

print scalar localtime;
while( my $chunk = <$inFH> ) {
#    print sysseek $inFH, 0, 1;
    local $/;
    my( $odds, $evens ) = ('') x 2;
    for my $idx ( unpack 'n*', $chunk ) {
        $odds .= substr $oddLU, $idx, 1;
        $evens .= substr $evenLU, $idx, 1;
    }
    print $oddFH $odds;
    print $evenFH $evens;
}

close $_ for $inFH, $oddFH, $evenFH;
print scalar localtime;

__END__
C:\test>u:ls -l 1Mx4096.db odd.bin even.bin
-rw-rw-rw-   1 user     group    124592128 Jul 28  2004 1Mx4096.db
-rw-rw-rw-   1 user     group    62296076 Jun 28 01:42 even.bin
-rw-rw-rw-   1 user     group    62296076 Jun 28 01:42 odd.bin

C:\test>junk 1Mx4096.db
Thu Jun 28 01:36:11 2007
Thu Jun 28 01:37:12 2007

C:\test>junk -SIZE=1048576 1Mx4096.db
Thu Jun 28 01:38:42 2007
Thu Jun 28 01:39:44 2007

C:\test>junk -SIZE=10485760 1Mx4096.db
Thu Jun 28 01:41:31 2007
Thu Jun 28 01:42:56 2007
[download]