You've nailed the problem directly on the head. For hitting 60Hz in FuryGpu, I actually render at 640x360 and then pixel-double (well, pixel->quad) the output to the full 720p. Even with my GPU cores running at 400MHz and the texture units at 480MHz with fully fixed-function pipelines, it can still struggle to keep up at times.
I do not doubt that a shader core could be built, but I have reservations about the ability to run it fast enough or have as many of them as would be needed to get similar performance out of them. FuryGpu does its front-end (everything up through primitive assembly) in full fp32. Because that's just a simple fixed modelview-projection matrix transform it can be done relatively quickly, but having every single vertex/pixel able to run full fp32 shader instructions requires the ability to cover instruction latency with additional data sets - it gets complicated, fast!
There's a new board by Trenz with a Versal chip which can do 440 GFLOPS just with the DSP58 slices (the lowest speed grade) and it costs under 1000 Euros, but you also need to buy a Vivado license currently.
Cheaper boards are definitely possible since there are smaller parts in that family, but they need to offer support for some of them in the free version of Vivado...
So my guess is that it would be quite challenging to implement a modern GPU in an affordable FPGA if you want more than a proof of concept.