You could certainly estimate the clock frequency in advance. The things that are going to cause trouble are transmission line effects (ie pulse length no longer >> wire length), and the usual digital logic critical path constraints: wire and gate delays; clock skew and drive strength; fanout constraints.
More decoupling doesn't help you once you have enough to prevent crosstalk through the power supply. Star-routing the power and ground may be a good idea.
I've done 20MHz. Coincidentally this is the limit of cheap scopes. This page claims 33MHz is achievable, and gives a good explanation of why: http://www.sigcon.com/Pubs/news/2_8.htm
Some good tips: https://www.pjrc.com/tech/8051/dev-board-wirewrap.html
Reccomendation to use the kind of board with built-in ground plane (sounds good if you can find it): http://www.williamson-labs.com/prototype-lt.htm
For IC availability, check your local Digikey. Note that 68k is still being manufactured as "Coldfire" by Freescale (with slight backwards incompatibility).
I haven't really done any wire wrap projects, just played with it a bit, but I really liked this page for general advice, he seems to know the art well:
Are there smart ways to use decoupling capacitors to get more?
How do you get a feel for how much room you have to play with as far as MHz? Is it just a case that you start with something small, and then go up until it breaks?
Are there practicalities of what chip generations is possible with wire-wrap? 6502 would be possible with wire-wrap. What about Motorolla 68k? (Also - what is the most sophisticated 68k chip that's still commercially available? Speed and memory addressing are important, MMU is not.)