How do I set the headers to "application/x-www-form-urlencoded" on a XML based API Call

I am looking over the documentation for the VerMail API and they specify that I need to set the headers to "application/x-www-form-urlencoded" but I have to send the data as XML.. I know this is automatic if I send the data in an array but how would I do it with XML?

This is the code that I have so far:

$xmlcontent = "
<api>
  <authentication>
    <api_key>".$apiKey."</api_key>
    <shared_secret>".$apiSecret."</shared_secret>
    <response_type>xml</response_type>
  </authentication>

  <data>
    <methodCall>
      <methodname>legacy.message_stats</methodname>
      <last>100</last>
    </methodCall>
  </data>
</api>
";

$xmlcontent = urlencode($xmlcontent);

$ch = curl_init();
curl_setopt($ch, CURLOPT_HEADER, 1);
curl_setopt($ch, CURLOPT_RETURNTRANSFER,1);
curl_setopt($ch, CURLOPT_URL, $url);
curl_setopt($ch, CURLOPT_POST, 1);
curl_setopt($ch, CURLOPT_POSTFIELDS, "XML=".$xmlcontent);
$content = curl_exec($ch);

print_r($content);

This is what I see on the source code when I run it:

HTTP/1.1 200 OK
Date: Fri, 23 Jan 2015 20:17:52 GMT
Server: Apache
Cache-Control: max-age=18000
Expires: Sat, 24 Jan 2015 01:17:52 GMT
Content-Length: 595
Connection: close
Content-Type: text/xml;charset=utf-8
Set-Cookie: BIGipServerBH-gen-80=235023882.20480.0000; path=/

<?xml version="1.0" encoding="utf-8"?>
<methodResponse><item><error><![CDATA[1]]></error><responseText><![CDATA[ XML Error: Please verify the XML request is valid.  For special characters please ensure you are using <![CDATA[ ]]]]><![CDATA[> blocks and url encoding data properly.]]></responseText><responseData><error><![CDATA[Not well-formed (invalid token) at line: 1]]></error><responseCode><![CDATA[425]]></responseCode></responseData><responseNum><![CDATA[1]]></responseNum><totalRequests><![CDATA[0]]></totalRequests><totalCompleted><![CDATA[0]]></totalCompleted></item></methodResponse>