I’ve had titles pop into my head very early in the process – I knew the titles for “A Gift of Fire, A Gift of Blood,” “Indigo Rain” and “Going Concerns” before I was very far into them – but I don’t think I’ve ever started with one.
Conversely I’ve had a few stories which have been awfully hard to title. I’m still not convinced there isn’t a better title than Kismet for my novel, but I’ve made my peace with it.
Otters In Space started as a title. I think I started claiming that I’d write a book called Otters In Space some day as far back as high school. I know I was claiming it in college. At that point, all I knew was that I wanted it to be hard sci-fi (like Arthur C. Clarke) but with talking otters.
Rules are made to be broken. That said, I do agree about trying to have uncommon, Googleable names. It’s not a requirement, but anything that makes you distinct and easier to find is worthwhile. Marketing and all that.
My approach has been to use real-world phrases as a basis. Which fits, only because my work is in the “real” world. “The Latte Segment” is (a translation of) a real Scandinavian demographic term which describes the main characters fairly well. Heck, first scene, rabbit drinking a latte. It’s perfect. It also took me three months and four other titles to find it. If you’re doing sci-fi or harder fantasy, though, that’s not really a good suggestion.
I like modest length, 2-5 words, but I think cadence is more important. “Your Heart is a Muscle the Size of a Fist” is long, but it flows well. There are only four actual “beat” words (Heart, Muscle, Size, Fist). It’s almost iambic in its flow. Doesn’t feel like 10 words. Try reading your title aloud and see how it flows; a sharp or gradual or sing-song title flow can affect the reader’s expectations, so that can be another subtle value.