This thing is really powerful once it sets up; few things can stop it. If you let it set up yet retain its 100% HP, you're pretty much fucked. However, there are a few ways to deal with this beast. I've been using it and it's one of the most powerful sweepers that I've ever used.
Grass-types: Ferroseed is the main answer here, as it resists all of Tirtouga's attacks and can hit past Sturdy with Bulket Seed. Lileep is also a great answer because it is immune to Water-type attacks and has the best defense out of all of them. Shroomish and Foongus work well too. They all have the bulk to take a +2 Stone Edge and OHKO with Giga Drain or shut it down with Spore. Stone Edge only does ~60-80% max to each, so it's not too tough. Just don't let it boost too much.
Scarfers: Tirtouga is really slow, so some faster Scarfers such as Murkrow, Mienfoo, or Chinchou can outspeed it and defeat it. The catch here is that they must be fast and bulky enough to take a +2 Aqua Jet, or a +2 Aqua Tail / Stone Edge AND an Aqua Jet if Sturdy is still intact.
Physically defensive pokemon: Hippopotas, Bronzor, and Slowpoke come to mind here. They have bulk / resistances that allow them to take a hit and reply back. However, if they're weakened, they can not work.
Fighting-types- Croagunk is the main one- immune to Water and resistant to Rock, it can take many hits, and simple heal back with Drain Punch and then Vacuum Wave. The damage it sustains is relatively little too as it can heal it off with Drain Punch. Evio Mienfoo can take a +2 Aqua Tail iirc (though maybe not) and KO with Fake Out + Drain Punch. Timburr and Machop have the bulk to take Aqua Tails and KO with Fighting type STAB.
So, the trick is to break its Sturdy before you try to counter it as that makes it a lot easier to handle, and the loss of one pokemon could prevent the loss of your whole team, if you lack the above counters / checks.
And @ above: I have absolutely never seen Superpower, Ice Beam, or HP Fire. If it carries those, it lacks priority / water STAB / rock STAB, so you can just switch to a different counter. EQ is also very rare, I don't think I've seen it more than once, ever.