What frequency limit can I expect if I move to a stripboard or even to
a PCB?
With a good multilayer board you should be able to get 100 MHz without much effort.
The VGA pixel clock for the modes I'm interested in is 31.5 MHz (which
I plan to divide to get around 8 or even 16 MHz for the CPU). But even
if the board can handle such frequencies, will the TTL chips be fast
enough?
No. Nope. And it gets worse.
Let's start with the horizontal counters. If you look at a data sheet you'll see that a 74LS161 is only guaranteed to be able to count to 25 MHz, although typically it will do 32 Mhz. Worse, consider the enable lines for the counter chain. The propagation delay from a clock to the TC output is worst-case 35 nsec, and the delay from CET to TC (which is needed at the second counter) is 14 nsec. Finally, if you look at setup times, the counters need the enable input to be stable for 20 nsec before the clock arrives. This means that the minimum clock period for a 3-counter chain is 35 + 14 + 20 nsec, or 69 nsec. This is a frequency of 14.5 MHz. It's true that some chips will do better than the minimum, as is evidenced by the "Typical" numbers, but you use them at your peril. If you use typical numbers and the chips are operating at minimum speed, you have no complaint.
And it gets worse. The RAM used in the video is a Hitachi HM62256 with an access time of 70 nsec (max). This is exceedingly marginal for a 10 MHz application, and is just not going to work at 31.5 MHz.
Can you, in fact, do what you want? Yep. I've done it. First, your timing counters and logic should use either 74F or 74AC/ACT for the horizontal counters. 74F, for instance, will allow a simple 3-counter chain to operate with a clock period of 32.5 nsec, which is a clock frequency of 30.7 MHz, and that's close enough to allow taking chances.
Second, the decoder setup he used for creating hsync and hblank is really sketchy. I won't go into details, but his use of mixed inverted/non-inverted signals invites what are called skew conditions which can trigger invalid "runt pulses" into the flip-flops, causing improper (and intermittent) pulses. In his case, he got away with it, but an unlucky collection of actual chips can show all sorts of problems depending on how well the chip speeds are matched.
The RAM will need to be replaced. With a clock period of 32 nsec, you'll need both fast buffers and fast RAM. The 74HC245s he used as buffers have a typ/max propagation delay of 7/~15 nsec, so planning for worst case you need to assume about 10 nsec delay from clock to counter output and another 15 nsec through the buffers, which only gives you about 6 or 7 nsec for the RAM to respond before the next clock comes around. You can get around this with, for instance, a register on the RAM outputs with a delayed clock, but you'll be depending on things like typical propagation delays and best-case temperature dependencies. It's doable, but may be unreliable unless you really know what you're doing.
Basically, I'm very surprised that the board shown in the video works as well as it does. Just as a start, there are no decoupling capacitors on the chips, and with the construction of the breadboards I'd expect this to be a problem.
If you really want to give this a try, be aware that, at a minimum you'll need an oscilloscope, and in come cases will need a fairly fast logic analyzer. I'd advise starting with a somewhat lower pixel rate than the 31.5 MHz clock rate - say 15.75 MHz, or a factor of 2 slower.
Be prepared for a fairly steep learning curve.
