Yes it is possible. You should pass the input parameter to the webservice call and its mapping. Then, in the mapping, use a microflow to create the new object and set the reference.
Update As far as i can see, the answer still holds, in the mapping lookup the object using a microflow ('custom' option), and pass that microflow the first argument and return it immediately. I used that successfully in the past. In the call activity, under 'Map to entities' a parameter dropdown should appear in which you can select the first input parameter.
How about setting a reference between the two input parameters (possibly with a third object to temporarily hold this info) so that you have access to both in the mappings?