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();
[download]

Update: After I posted this, I realized that you were using https so I updated the port from 80 to 443.