Over the counter medicine is one you can buy in a chemists or a pharmacy that does not require a doctors prescription.  It should be effective with scientific background and research that proves its efficacy.

Patent Medicine has been "patented" that is an element of its design has a patent connected to it.  It does not mean that it works, after all, "patent applied for" does not mean anything more than a document has been filed.  Historically even the term Patent did not mean that a patent had been applied for merely that it was a branded product.

So the critical difference is 1) it works, 2) who knows?