For something like this (huge scale operations), I would recommend investigating <executeSqlUpdate>, as in addition to errors like this AXL has throttling mechanisms that will kick in when data sets become gigantic.
Via a SQL query, you can add/remove device associations one at a time, or at least more efficiently in bulk (for example 100 at a time.)
Check the Data Dictionary for your version of UCM for definitions of the tables/fields/relationships in the UCM database, the table you will likely want to manipulate is 'applicationuserdevicemap'. Assuming you already know the user's and device's primary keys (UUIDs) the request might look something like (untested

<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:ns="http://www.cisco.com/AXL/API/7.1">
<soapenv:Header/>
<soapenv:Body>
<ns:executeSQLUpdate sequence="1">
<sql>INSERT INTO applicationuserdevicemap (description,fkapplicationuser,fkdevice,tkuserassociation) VALUES ("some description',deviceUUID,appuserUUID,1)</sql>
</ns:executeSQLUpdate>
</soapenv:Body>
</soapenv:Envelope>
Where tkuserassociation of '1' means a regular CTI controlled device (see the 'typeuserassociation' table).
Informix syntax guide: http://publib.boulder.ibm.com/infocenter/idshelp/v10/topic/com.ibm.sqls.doc/sqls548.htm