..., except that shelling out for each file is really expensive

Yes, it is. But unless you are sending thousands of 16KB files, the price should be negligible.
Did you take steps to identify the bottlenecks in your process or are you just guessing?
You are not giving us any information about the "provider" or details about their API, but I think that parallizing the process, as in upload multiple files at once, could speed things up.