Oh, there's a three line non-recursive solution as well, using the same algorithm (as the recursive solution). I just find recursion much easier.

sub cross {
    my @r = [];
    @r = map {my $l = $_; map {[@$_, $l]} @r} @$_ for @_;
    @r;
}
[download]

What I don't understand about the Perl6 solution is the need to count how many elements will be returned.