Frequency is going to be tough, just given the fact that we don't have records which can give us assurances of a full and complete picture, so we can only really talk about specific places and periods rather than "the middle ages" as a whole.

I've written previously about a specific form of trial by combat here, which was wagered in certain cases dealing with property claims in England. I don't discuss numbers there specifically, but to expand briefly, in studying wager of battle, M.J. Russell scoured English court cases specifically for 1201-1250. In that window, there were 123 cases which resulted in combat (cases of all types, not just property cases!). He found an additional 103 cases where wager of battle was offered, but the case was settled before reaching that point, or the fight otherwise didn't happen. He found 372 additional cases where the possibility was mentioned in the record, but no wager was offered. Of course, the one additional factor that he doesn't spell out is how many total cases were reviewed...

Still though, the main conclusion that he reaches is decently supported by those numbers, namely that it was not that common a way to decide a case. Keep in mind that it was only valid in the first place for cases where there was no compelling evidence one way or the other. Someone caught red handed over the body, covered in blood, holding the knife, by a dozen witnesses, wasn't going to be allowed to wager battle to prove their innocence! So it was already a smaller subset of cases, such as with property cases above where there were two competing claims without documentation that favored either. And even in the cases where it could be uses, while a fair number talk about the possibility, a minority of those - roughly 1/5 - actually carried through all the way to the field. The procedure only became more and more rare in the latter half of the 13th century and beyond, with the fact that what cases we do have records for go into so much detail speaking to just how rare and interesting they were to observers.