tt_dan: Actually I did send a paper documenting the algorithm itself to a conference and it was accepted. The journal version includes this plus a detailed comparison of the method against recent techniques. However, truthfully, the benefits of using my method are somewhat marginal and only occur on a very narrow type of data set.

What you feel is pretty common. In fact, it has its own wiki page:

For the full last year I've been stuck on a paper I've been writing. The paper documents the workings of a new algorithm I made to solve a computer vision problem. We submitted it to a journal and it was rejected on the basis of not having enough theoretical novelty. I made a lot of major modifications, then submitted it to a different journal, who rejected it for mostly similar reasons (and this time the reviews were much more critical, even though to me it seemed like a better paper).

Now that I've been working on this problem for so long I can see that there are good reasons why it wouldn't get accepted. It really doesn't offer anything new to the table. If I were a reviewer I would reject it. I feel like I am wasting my time on this and that I should cut my losses and try to scrape up what I have and work towards another paper. I am already 2 years into my phd, I don't want to waste any more time.

My supervisor has been pushing me to submit the paper. He has his own concerns - getting grants and pushing phd students through the door, and I can see why he wants to do this, despite being vaguely aware of the flaws. But I am certain the paper won't get accepted. I am certain that ahead lies months and months of rejection and heartbreak (and not to mention my supervisor's view of my abilities steadily declining). I don't want to risk that.

I really don't know what to do here. Has anyone been in this situation before?