"Has anyone found a correlation between the number of frogs/items/gems/Blue Magics/enemy's level/etc and the amount of damage Quina deals?"

There is none. Quina's Forks don't have the same minimum damage limits that other weapons do. If her base attack power is 11 that is the minimum s/he will do at any level with any strength. That doesn't make it completely random (s/he isn't capable of doing 9999 with a physical attack at Lv.1 for example), but it makes the range of damage wide enough to seem completely random.

Vivi's Comet and Meteor follow the same sort of formula.