I'm following the documentation on updating an object with a relationship field, but I'm getting an error. The documentation says to format the xml as such when referring to a relationship field:

<RelationshipName>
  <sObject>
    <IndexedFieldName>rwilliams@salesforcesample.com</IndexedFieldName>
  </sObject>
</RelationshipName>

In my case the xml looks something like this:

<?xml version=\"1.0\" encoding=\"UTF-8\"?>
<sObjects xmlns="http://www.force.com/2009/06/asyncapi/dataload">
  <sObject>
    <location_external_id__c>1234</location_external_id__c>
    <Name>My Location</Name>
    <Account__r>
      <sObject>
        <account_external_id__c>7890</account_external_id__c>
      <sObject>
    </Account__r>
  </sObject>
</sObjects>

This is an attempt to upsert to a custom object (Location__c) with an external id api name of 'location_external_id__c' that has a text field called 'name' and a Master-Detail(Account) field with relationship name 'Account__r'.  Account has an external id field called account_external_id. As far as I can tell this is all following the documentation for the bulk api. However I get back an error like this:

<results xmlns="http://www.force.com/2009/06/asyncapi/dataload">
  <result>
    <errors>
      <fields>Account__r</fields>
      <fields>sObject</fields>
      <fields>account_external_id__c</fields> 
      <message>Location__c: bad field names on insert/update call: Account_r, sObject, account_external_id__c</message>
      <statusCode>INVALID_FIELD_FOR_INSERT_UPDATE</statusCode>
    </errors>
    <success>false</success>
    <created>true</created>
  </result>
</results>

This looks to me like the Bulk API doesn't know anything about relationship fields despite what the documentation clearly says. Hopefully I'm just doing something wrong, does anyone have any ideas?