I ran into a similar situation. I was using parameterized queries to perform inserts/updates/deletes for a desktop application. The initial inserts down onto the client could exceed 400,000 inserts for a given table while after that I just pushed down changes. This works well and is lightning fast on a desktop. Then I started doing the same thing on a mobile device and found inserting 300-400 thousand rows taking a few minutes or so.
I decided this was just not good enough so I decided to ditch parameterized queries entirely. I rewrote my import/update routine at the cursor level, creating records and setting column data for inserts, and seeking to index values and setting column data when doing updates. After the change I'm now pulling in multiple hundreds of thousands of rows in seconds instead of minutes.
Another tactic I used is when synchronizing data, I have my client send up sets of index values for the data I'm synchronizing and then the server returns data so that all my inserts, updates, and deletes are pre-seperated, allowing the client to focus on each operation exclusively.