The prefix, in general
Voltaire wrote The Age of Louis XIV, published posthumously in 1781. This seems to be the first work with the epic prefix "The Age of". This is, of course, non-fiction but with the correct context. (Reverand Richard Hurd's Moral and Political Dialogues was first published in 1771 and had a section titled "On the age of Queen Elizabeth", but this was a section title as opposed to the overall book title.)
Thomas Paine's famous The Age of Reason followed soon after, in 1794.
In regards to fiction, Thomas Beck wrote The Age of Frivolity: A Poem in 1820 and George Lunt wrote The Age of Gold and Other Poems in 1843. There were also several books in the 1880s and 1890s attempting to tie Norse mythology to geological and astronomical events, all titled The Age of Ragnarok.
By the mid-to-late 1800s, a great many books had "The Age of" prefix. It was quite fashionable at this point to use it in titles of non-fiction, fictional prose, and fictional poetry. 1920 saw the famous The Age of Innocence by Edith Wharton, for example.
The prefix, in SFF
Now, as for science fiction and fantasy, the "age of" prefix doesn't seem to have enjoyed popularity until the 1980s. The catalyst could have been the intense interest in "The Age of Aquarius" in the New Age movement of the 1960s and 1970s.
By the 1990s, we had these developments:
The Wheel of Time series by Robert Jordan (began in 1990) speaks frequently of "the age of Legends"; it's not the title of a book, but given the influence of this particular series, and since we are trying to chart the history of the prefix, I feel it should be included
Horror master Clive Barker wrote The Age of Desire in 1994
Marvel published the crossover comic series Age of Apocalypse in 1995-1996
Continuing with comics:
- In 2013, Marvel launched the Age of Ultron crossover series. Whedon's Avengers film "borrows" the title of this series, but not the plot. (Thanks to @CreationEdge and @Gorchestopher on this one!)