It's far from clear what kind of being the River-daughter was, and so it's very hard to estimate her dates, other than to say that she was definitely extant in III 3018, when she met Frodo and his companions. She seems to have been some kind of spiritual being, which might very well imply that she was immortal, but on the other hand the fact that she was a 'daughter' suggests that (unlike the Ainur, for example) she came into being after the world was created. There are even hints that she may have been relatively young at the end of the Third Age (for example, we know from the poem "The Adventures of Tom Bombadil" that she wedded Tom relatively late in that Age).

Our only real hint about the River-daughter's place in Tolkien's universe comes from a comment to a correspondent in which he referred to her in a symbolic sense, as representing seasonal changes (The Letters of J.R.R. Tolkien, No. 210, dated 1958). It's far from clear how we might interpret her existence in a more literal way - if indeed we're intended to do so at all. For more on this topic, see the entry for Goldberry.