This came out probably in the mid-90's although I may be wrong. Here's the plot summary, albeit extremely hazy:
- Set on a planet colonized by modern humans
- Planet's continents are seeded with genetic clones/recreations from Earth's past and each continent contains only flora and fauna from a specific epoch
- Ocean going carnivorous dinosaurs (Plesiosaurs?) prevent species from crossing oceans
- Story is set on one continent that is home to modern humans, Neanderthals, and other archaic humans and other hominids.
- Protagonist is a Neanderthal who's in love with a promiscuous human girl who works at a trading center or shop or bar
- Goes on a quest to stop an invasion by a horde of archaic humans
- Aided by two brothers who are not modern humans or Neanderthals but ride mammoths
- He succeeds
I know. Plot is a little bizarre but it's a real book. Thanks!