OK, I just spent two hours figuring this out. Make sure you are using ssleay (not openssl)

Here is the code to properly setup mechanize to use a private proxy:

use WWW::Mechanize;
my $proxy='proxy.host.net:8080';
my $proxy_user='proxy_username';
my $proxy_pass='proxy_password';
$ENV{HTTPS_PROXY} = 'http://'.$proxy;
$ENV{HTTPS_PROXY_USERNAME} = $proxy_user;
$ENV{HTTPS_PROXY_PASSWORD} = $proxy_pass;
my $mech = WWW::Mechanize->new();
$mech->agent('Mozilla/5.0');
$mech->proxy('http', 'http://'.$proxy_user.':'.$proxy_pass.'@'.$proxy);
$mech->proxy('https', undef);
$mech->get('https://www.somehost.com/');