As noted in the comments, Julian May's Saga of Pliocene Exile fits well.
In the (relatively) near future, instead of sending criminals to prison, they're sent on a one-way time travel jaunt to the distant past. Surprisingly, they arrive to discover that they're even worse off than expected; two opposing alien forces are running things, and pick up humans to be their slaves when they're sent back.
However, humans have begun to develop "metapsychic" abilities (as seen in May's related books, Intervention and the Galactic Milieu trilogy (Jack the Bodiless, Diamond Mask, and Magnificat)); and, several of our time-displaced humans seem to have latent abilities that get jump-started into activation by the time jaunt, and/or the stressors involved.
And, yes, what was dry land when our viewpoint characters arrive is the Mediterranean Sea by the time they're done.
The books are:
- The Many-Colored Land
- The Golden Torc
- The Non-Born King
- The Adversary
Oddly enough, this and The Gandalara Saga came out at about the same time, and both included the creation of the Mediterranean Sea.