I always thought so, too.  Interestingly, according to Devel::Size, the memory usage isn't all that different:

use Devel::Size qw(total_size);

my @a;  push @a, [$_,$_] for 1..2**16;
print total_size(\@a);                   # one array of pairs

my @b;  push @b, $_ for 1..2**16;
print total_size(\@b) * 2;               # two arrays

__END__
4964080
4740496
[download]

(tested with perl, v5.10.1 (*) built for x86_64-linux-thread-multi, Devel::Size-0.72)

PS: although there is nothing random in the data, the sizes reported by Devel::Size vary by up to 15% from call to call (i.e. on some occasions the one array with pairs uses even less memory than two separate arrays). Why is that?

I don't trust Devel::Size, I prefer measuring externally:

my @a;
my @b;

for (0 .. 2 ** 16 - 1) {
    if ($ARGV[0]) { 
        $a[$_][0] = $_;
        $a[$_][1] = $_;
    }
    else {
        @a[$_] = $_;
        @b[$_] = $_;
    }
}

system "grep ^VmSize /proc/$$/status";

__END__
[download]

Without an argument, I get VmSize: 11460 kB, with an argument I get VmSize: 16636 kB. Repeated runs vary by less than 10 kB. That's a difference of 45%.

However, I do notice a difference using total_size as well. Adding a say total_size(\@a) + total_size(\@b); at the end, I get:

VmSize:       11844 kB
3670208
[download]

and

VmSize:       16996 kB
10748112
[download]

Almost 3 times the amount of memory with array pairs than without, according to Devel::Size;