How to optimize this SQL delete
Per the other example - step 1 should be to get out your profiler.

In any case - 
I suspect you would get significantly reduced round trip times by taking advantage of JDBC batching capability. Here's an example: http://www.tutorialspoint.com/jdbc/jdbc-batch-processing.htm (see the second one - using a prepared statement).

In short - you create your DELETE prepared statement, drop the values into a batch, and then execute the batch in one go. Use a prepared statement to reduce parse time for the server.

Depending on if you want to ramp up the complexity, you might want to split the rows into tasks and run them in parallel threads.