Probably because some ad executive linked them, back in the day, and the marketing guys really pushed it.
There's no question mint provides a pleasing freshness, and, in fact, has been used as a breath freshener for centuries. But so, too, have other herbs been used that way.
The ironic thing, of course, is that perfumes originated to mask odors that result from less-than-sanitary conditions. For people who didn't understand mouth and tooth care, breath freshening was important. By chewing a few mint, or basil, or rosemary leaves you covered up really bad breath. People like ourselves, who brush regularly etc. shouldn't have bad breath to begin with. But we still obsess on using perfumes.