The end-result of this problem was rather simple, but is a biiit hacky.
When I create my E4X object I simply put in a placeholder element... example...
var myData = ['apples','oranges','pears','grapes'];
var myFruit;
for( var i=0; i<myData.length; i++ ){
myFruit += <fruit>{myData[i]}</fruit>;
}
var request = <soapenv:Envelope>
<soapenv:Header></soapenv:Header>
<soapenv:Body>
<MyFruitList>
<fruitList/>
</MyFruitList>
</soapenv:Body>
</soapenv:Envelope>;
Later, I'm converting the whole object string before I submit the SOAP request.. so after the string conversion I simply did a string replace.
var requestString = request.toString();
requestString = requestString.replace("<fruitList/>",myFruit);