What counters Mei?
What makes Mei threatening is her one-two combo. Once she locks you down with her primary fire, she can use her alternate to finish you off. However, her primary fire requires some time to immobilize and she can only target one enemy at a time. This leaves her weak to grouped assaults, burst damage, and hit-and-run attacks.
Ignoring coordinated assaults as they might be difficult for pub groups to pull off, Mei's short range leaves her weak to mid-range and long-range heroes such as S:76, Widowmaker, Hanzo, and Pharah. Provided they keep out of range, that is.
Heroes with high burst damage like Roadhog's hook+scrap+melee combo or McCree's alternate fire can also deal with Mei though this is a riskier proposition as they have to get in close range and not landing their burst leaves them open to be frozen and icicle'd.
Somewhat counterintuitively, heroes with high mobility such as Tracer and Genji also have an advantage against Mei, though this is very dependent on tactics. While Mei can lock down these squishy speedsters, she needs 2 seconds of consistent damage to do so. Therefore, she excels at prolonged encounters and Tracer/Genji need to realize this.
Don't expect to kill Mei in the first encounter. She has 250 health and most likely her Ice Block. Instead, whittle her down with guerilla tactics, making sure to use your high mobility to dip out of combat every now and then to avoid her freeze. If you have your ultimate, bait out Mei's Ice Block. While she can exit her Ice Block at any time, most Mei players will choose to spend the full duration to recover as much health as possible. Either count the duration (4s) or listen for the audio cue and use your ultimate right as she comes out of Ice Block. Tracer's ultimate will one-shot her and Genji needs 3 strikes (although in practice, it's usually 2), which he should be able to accomplish in 2s.
Killing her from a distance.
Mei can only freeze at close range and it takes several seconds to do so. That is, unless she uses her Ultimate to do it (which is in a circle from where the item lands).
Mei also doesn't have the DPS to kill a Tank by herself.
Mei strength comes from her ability to freeze one of her opponents. To do so, she has to use her freezing ray a few second on an enemy at a relatively close distance.
If you analyze my first two sentences you can guess what are Mei's weaknesses:
freeze ONE of her opponents
By grouping with your allies, it won't be easy for Mei to freeze you and shoot an icicle through your skull. Moreover, if she is alone against your team and use ice block, you should get plenty of time to decide to flee of finish her!
use her freezing ray A FEW SECONDS
Mei doesn't have the biggest dps of all the Overwatch characters, as I said earlier, she rely on her crowd control more than on her damages. This means that if you out damage her in two seconds, you win. Roadhogg is a good choice, but while playing this guy you are more likely to play close to your team mates, meaning a good Mei should not be here (Mei is probably killing your lone mates).
My favorite character to kill Mei (and my favorite character overall) is Reaper. Once you get close to someone you can deal a ton of damages really fast. If you are really good, you can kill her in two shots (she probably won't have time to use her ice block). Moreover, if things turn bad, you can still use your Shift ability to flee, remove the slow effect of Mei's gun and reset the freezing process.
a relatively CLOSE distance
If Mei can't freeze you she will have an hard time to kill you. Stay far away from her and use your mobility to flee/chase her. A good Widowmaker/Hanzo can snipe her or flee easily by climbing walls.
Finally, don't forget that taking your opponents by surprise, knowing your enemies, knowing your character and knowing maps will help you to be a better player.