Here is Sheldon's take on it: Your backbrain should be niggling you when you start to get some punctures or the fabric layer/belt (which gives the structure of the tire) of the tire is about to show or is damaged. Unlike a radial, where the tire is integral to keeping the wheel working, all a tire has to do is protect a tube. The rest of the stuff is aesthetic. Proper inflation is important for controlling wear though.
Schwalbe's marketing material says that Schwalbe Marathons should last between 6000 km and 12000km, but I'd be inclined to say thats conservative in good riding conditions - I have much lower quality tires than Schwalbe Marathons which are closer to the higher end of that range and show no signs of giving up (this is for commuting, and they have around 7000 miles on them, but this is on a 26" rigid mountain bike so significantly bigger tires than you're likely considering, so maybe not a fair comparison).