It doesn't appear to be possible to do anything other than a plain text FeedItem with the SOAP API.
I tried the following directly POSTed to the SOAP API.
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:urn="urn:partner.soap.sforce.com" xmlns:urn1="urn:sobject.partner.soap.sforce.com">
<soapenv:Header>
<urn:SessionHeader>
<urn:sessionId>00D300000000001!AQ0AQMNot_My_Real_Session_Id_Get_Your_Own1miwAs5icUg</urn:sessionId>
</urn:SessionHeader>
</soapenv:Header>
<soapenv:Body>
<urn:create>
<!--Zero or more repetitions:-->
<urn:sObjects>
<urn1:type>FeedItem</urn1:type>
<!--Zero or more repetitions:-->
<urn1:fieldsToNull></urn1:fieldsToNull>
<urn1:Id></urn1:Id>
<!--You may enter ANY elements at this point-->
<urn1:Body><p>Test Post 4 with mention of @Daniel Ballinger </p></urn1:Body>
<urn1:ParentId>0064000000OXBSI</urn1:ParentId>
<urn1:IsRichText>true</urn1:IsRichText>
</urn:sObjects>
</urn:create>
</soapenv:Body>
</soapenv:Envelope>
That created a FeedItem record that was identical to on I created directly in the UI with an active Mention of myself. Or at least, identical in how the SOAP Partner API sees the FeedItem records.

I suspect you will need to use the REST based Chatter API to define a richer Feed Item Body with message segments for mentions.
There is an idea - Add @mention to Chatter FeedItem body via Apex Code or AJAX Toolkit, but that appears to have mostly focused on the Apex Chatter integration.