Do we know that absolutely? Is is possible that a)They are lying in order to look more impresive to mortals in order to get more belief-juice. b)They think they are eternal, but are mistaken/have false memories simply because mortals believe that they are eternal. c)Maybe they were formed by mortal belief, but that belief gave them so much power that they were basically able to timetravel to a time before humanity. A bit silly perhaps, but in book 5 Harry says there are beings that exist in time in different ways and in GS we have Uriel imply that he is not limited to linear-time.