If you are going to use the four argument credentials, you need to pass the right data into it. Location is <host>:<port> as documented in LWP::UserAgent.
Try this totally untested piece of code and see if you get better results.
#!/usr/bin/perl
use strict;
use warnings;
use WWW::Mechanize;
use Crypt::SSLeay;
my $mech = WWW::Mechanize->new();
# Don't pass the full URL as the location in the call to credentials!
my $server = 'api.datamarket.azure.com';
my $url = "https://$server/Bing/SearchWeb/Web?Query=%27Xbox%27&$top=1
+0&$format=JSON";
my $loc = "$server:443";
my $account_key = "<my key>";
# Yes, WWW::Mech still supports LWP::UserAgent's four arg credentials
$mech->credentials($loc, '', '', $account_key);
$mech->get($url);
print $mech->content();
Update: After I posted this, I realized that you were using https so I updated the port from 80 to 443.