It seems to me that you should only worry about the genre of your story when it is finished. Trying to ensure that you have fulfilled all the criteria for a certain genre seems an ideal way to lose sight of your own goals for the story.

The word's denotation is "kind" or "type" and at one time, I believe, referred to the distinctions between essays, poems, epics, novels, romances (when that word denoted adventure stories), plays, and so on.

It has now taken on the connotation of "marketing category" as yanos points out, and the purpose of a marketing category is basically to tell the bookseller which shelf to put the book on.

Also, as yanos points out, sometimes there is an awful lot of overlap between marketing categories.

The main reason people worry about marketing categories is that it will often help to sell a story if the sales people can put it into a marketing category, and it will often hurt a story's chances of being purchased by a publisher if the sales people think they can't put it into a marketing category.

If the story is good enough, though, it can actually start its own marketing category (also known as "books like that" until a more specific name comes along). (An example of that is William Gibson's NEUROMANCER which got the marketing category of cyberpunk going. Now those books have been absorbed back into the marketing category of science fiction, but at one time, they were considered by some to be in a class by themselves.)

However . . . .

There are a few things to think about. Most writers make a name for themselves writing one kind of story. For all practical purposes Stephen King is known as a horror writer, even though he's written mainstream fiction, thrillers, fantasy, and wonky sci-fi (as opposed to SF). Orson Scott Card is known as a SF writer even though he also has written mainstream and fantasy. So in a certain sense, you as a writer have to determine what kind of stories you most often like to tell so that you know what genre to market your work as. That's how you develop an audience and make a name for yourself.

And there's another reason, too. You have to know what to read. Yes, you need to read what you want when you want, but if you've determined that you a horror writer (by which I mean you see patterns in your reading habits and your story telling), then, by gum, you better start reading a lot of horror. You better be well versed in the history of the genre. You better know what you're doing if you want to succeed.

Does that make sense?

An annoying autobiographical proof:

I know this from experience. When I started writing, I decided in some a priori way that I wanted to write SF and fantasy. Try as I might, I kept failing. Finally I had to admit that I'm not much of a SF and fantasy fan. Oh, don't get me wrong--there's a handful of SF and fantasy stories and authors I enjoy, but not many. I based my decision because of those novels that I thoroughly enjoyed. But once I released myself from that burdern and began to write what I wanted, I found that I tended toward mainstream, horror, and contemporary fantasy (or whatever the hell it's called). I think this kind of problem plagues those who come to writing later in life; we lack the childlike attitude to be free when it comes to writing. We need to develop a five-year plan, have our goals in line, and work to achieve it. And that simply doesn't work. It didn't work for me, at any rate.

I thought I was headed straight for the science fiction ghetto, but the more I wrote, the more I realized I hated trying to get the science believable and accurate. I just didn't want to do that much work, work defined as tasks which I loathed.

So I backed away and asked myself what kind of books did I enjoy reading? More importantly, what books changed my life the most? Without question, the two books that changed my life the most were LOTR and John Crowley's Aegypt. That was my "a-ha" moment. I realized I wanted to write the kind of stories I loved to read for myself. That puts me pretty squarely in the fantasy genre, and I feel quite happy and comfortable there.

It is no less work, but it work defined as tasks which I enjoy doing; they are of a different nature. And I do not feel out of focus about my writing. When I get published, I will not worry one bit that "fantasy" will be its display category. I feel no urge to write any other kind of fiction. Maybe I'm a little singular in that way. I've notice that some of the best fantasy (and SF, too) sometimes escapes from the ghetto and is found on the literary fiction section; for example: Neal Stephenson, John Crowley, J.K. Rowling, and Susanna Clarke.