It is not getting lost. Your URL ends up being authenticate.cgi?destination=mypage.cgi?key=1&foo=bar, which makes foo=bar parameters to authenticate.cgi rather than part of its destination parameter.

You want something like

use URI::Escape;
print(
    "authenticate.cgi?destination=",
    uri_escape( $query->url( -query => 1 ) ),
);
[download]

Or you could use URI to build the URL which transparently handles all escaping as necessary:

use URI;
my $dest = URI->new( "authenticate.cgi" );
$dest->query_form( destination => $query->url( -query => 1 ) );
print $dest->as_string;
[download]

In either case, you get this properly escaped result: authenticate.cgi?destination=mypage.cgi%3Fkey%3D1%26foo%3Dbar