When we say would have, could have, should have, must have, might have, may have and ought to have, we often put some stress on the modal auxiliary and none on the have. We may show this in writing by abbreviating to could’ve, must’ve, etc. (Would can contract further by merging with the subject: We would have → We’d’ve.)
Unstressed ’ve is phonetically identical (/əv/) to unstressed of: hence the widespread misspellings would of, could of, should of, must of, might of, may of, and ought to of. Negative forms also appear: shouldn’t of, mightn’t of, etc. This explanation – that misanalysis of the notorious schwa lies behind the error – has general support among linguists.
The mistake dates to at least 1837, according to the OED, so it has probably been infuriating pedants for almost 200 years. Common words spelt incorrectly provoke particular ire, sometimes accompanied by aspersions cast on the writer’s intelligence, fitness for society, degree of evolution, and so on. But there’s no need for any of that.