ALCON,

My wife and I have been engaged in a great debate, and a simple google search has failed to resolve it.  We pose to you this inquiry involving the use of "could have" "should have" and "would have" and whether or not using them alters verb tenses following them.

I did the dishes.  (correct)
I done the dishes. (wrong)

I would have did the dishes. (wrong?)
I would have done the dishes. (right?)

Does the use of would have, could have, or should have alter which is the correct choice to use properly?

The reason why a Google search does not answer your question is because it is way toe specialized and beyond the grasp of Google technology. Google simply sweeps up everything that is out there on the web, and there are no enforced standards for what goes out on the web, minus some stuff about illegal content. You are interested in a specific form of English, Normative English, but there is no way to (a) authoritatively determine whether a web page follows the rules of Normative English or indeed (b) to absolutely determine what the rules of Normative English are. Very much of the content of the web is in non-Normative English, indeed a huge amount is in non-native English, to the point that utterances ostensibly in English are really the result of e.g. a Chinese speaker learning enough English to post a question or comment. There are a number of people trained in Normative English, and through apostolic tradition we know that "I did the dishes" is Normative English", likewise "I have done the dishes". You want to direct your question to them.

One weakly useful Google approach is the literal search, where you put sample pair in quotes and count the hits. "I did the dishes" gets twice as many hits as "I done the dishes". In the case of "I would have did/done the dishes", the number of hits is so low that you learn nothing. With a more generalized search for "I would have did/done", you find that "I would have done" is 7-fold more popular; the most general search for "have done" vs "have did" favors "have done" by about 250-fold. This is a very crude method, because included in the set of hits for "I would have did" are many examples of Normative English grammarians saying "You can't say 'I would have did'".

Linguists are probable very bad people to ask about this, because we are aware that this is a property of Normative English, and not a general property English. Usually if you direct such questions to a Normative English focused audience (such as English Language stack exchange, or any of a number of English grammar fora), the audience will ignore non-Normative dialects and just say "You can't say 'have did'".