By using Øysteins approach I was able to get the time down to 2.4 seconds on my machine, on which the client  and stored procedure code took around 12 seconds. The best I could get on the latter, tweaking page cache size and page size, was around 8 seconds.
By cheating and removing some durability guarantees, I got down to a best time (not quite stable) of 1.5 seconds using Øysteins suggestion.
I was surprised of the high disk activity seen when running the code. Lots of writes are taking place, which I did not quite expect for Øysteins query. But I do not know the implementation or the algorithm being used.
There also seem to be some overhead invoking a stored procedure, as the client  code is faster. This would of course look different if the network JDBC driver was used, as you wouldn't have to transfer the data over the wire.
To me it seems what takes most of the time is updating the result table.
So in short, no fresh ideas! Anyone else?
I didn't try using batches for the updated though.
PS: Note that your pageSize setting is invalid (must be one of 4096, 8192, 16384, or 32768) and Derby will silently ignore it and use the default...
 Note that client in this case still refers to the embedded driver, but the code composing the stored procedure is invoked from the driver side instead of "inside" the database.
I set pageSize to 32768, but result time seems near 11-12 sec.