You have a bug:

map {
   s/.../.../seg;         <-- Escapes the index.
   $form_data{$_} =~ ...  <-- Should be using unescaped index.
   ...
}
[download]

Not to mention that modifying $_ without localizing it is dangerous.

Fix:

$form_data = join '&',
             map { my $key = $_;
                   my $val = $form_data{$_};
                   $key =~ s/([^A-Za-z0-9])/sprintf("%%%02X", ord($1))
+/seg;
                   $val =~ s/([^A-Za-z0-9])/sprintf("%%%02X", ord($1))
+/seg;
                   "$key=$val" }
             sort keys %form_data;
[download]

You should be using URI::Escape anyway:

use URI::Escape qw( uri_escape );

$form_data = join '&',
             map { my $key = uri_escape($_);
                   my $val = uri_escape($form_data{$_});
                   "$key=$val" }
             sort keys %form_data;
[download]

Or even better yet, use URI::QueryParam:

use URI;
use URI::QueryParam;

my $uri = URI->new(...);

$uri->query_param($_ => $form_data{$_})
   foreach sort keys %form_data;
[download]

You have a second bug: The specs for this encoding (application/x-www-form-urlencoded) specifies that fields must be in the same order as the one in which they appeared in the HTML form. You're sorting them alphabetically instead.