The genre of the game matters a lot. Horror games tend to go adjectives and words that set moods. Action games tend to take a plot point and bring it out, or make a slogan (think Gears of War, Halo, Call of Duty). Fantasy games (what you're probably going with) can be trickier. They usually divulge something do with the setting and plot. If your setting and plot are particularly unique, then this'll work.
For example, war of the elements is a great name for a game about a war of elements... It's just that such a game is unbelievably cliche.
'Tales of' is a setting word that applies to pretty much every game ever, which is why it is cliche.
Course, titles don't have to be really imaginative, just draw from the plot. Take the film Kill Bill, the title is just what the film is about. Halo is about a planet called Halo. Hell, if your game makes up any cool sounding words for its terminology, you can use that for a title.
There's no need to go out of the way dressing up your title. It'll only make it worse.
Early adventure games were just named after characters (Mario, Spyro, Crash Bandicoot) and they weren't bad games, in fact, they were good, and the titles made sense. World War Two is what we call the most gruesome war in human history. It's not imaginative, but it captures it well.
So basically. Pick the most defining aspect of your game, the part that sets in apart from any other game, and run with it.
Think God of War. It was named because the main character was, in fact, a God of War. It really is that simple