How to overcome discouragement on finding major error in work just before paper submission?
I think that the best way to overcome your situation is to realize that nothing out of ordinary happened - to err is human. In my opinion, research is about discovering truth and enriching knowledge (including the one of the researchers'). And making mistakes is a natural part of the process. I would just discuss my work with advisor openly and do my best to learn from that.

I don't think that you have wasted anybody's time. I (along with many other people) believe that negative results are also valuable (for example, see this paper, this journal and this workshop). The same applies to other results, such as similar to existing results, not impressive results, etc.

As for strategies for not making mistakes, I don't think there are any to prevent them completely, as I said, but you can reduce their probability by not advancing too fast in your research (i.e., rushing to obtain results or to publish) as well as asking feedback on your work from other people beyond your advisor or other people closely involved in the research (perhaps, even, from other disciplines, in order to obtain opinions, based on different perspectives).