In general, if you have a number as an adjective, such as five percent of cases go unsolved, 76 percent of them voted in favor, or 50 percent of coin throws land on heads, you use percent of.
If you have roughly the same percentage of men and women, a low percentage chance of failure, or a policy meant to decrease the percentage of drivers without insurance from 25% to 15%, percentage of is more common.
So, in your example, I personally would use frequency as a percentage of the total in a sentence. The other would be perfectly understandable too, and I may favor it (not sure though) as a graph title.