A Paleolithic tribe would usually just call that River over there "the river". But do we know when humans began giving places and geographical features names, like Tigris or Euphrates of Nile?
We have no way of knowing what any paleolithic tribe called anything, but all the evidence we have of the very earliest languages we can access (which are late neolithic, at best) suggests that place names were already common. In fact, some of the most common likely survivors of pre-Indo-European languages in Europe are from place names. For instance, in Greece, place names with the ending -unthos (like Olynthos) are often argued to be remnants of pre-PIE substrates.
See here for a good discussion.