Now that question will open a can of worms! Basically, there is no way to accurately answer that question because there are so many factors involved. That being said...
The "quick" answer is that I wouldn't be concerned until the signal frequencies get near 1 MHz. Between 1 and 10 MHz I would be extra careful. And above 10 MHz I would have a PCB made. Of course there are exceptions, and this is what I would do, etc. But as a rough order of magnitude place to start, it works.
There are many issues involved with this, and I'll try to cover them here...
As others have stated, it's not the signal frequency but the rise/fall time of the signal edges. If you can slow down the edges (but not too much) then you'll have an easier time. FPGA's are great for this because you can change the slew rate and drive strength of the I/O Pins. In a synchronous system, this is more important on the clock lines than the data lines (I'm not saying that data isn't important, however.)
While doing proper signal termination is important, you can't do signal termination without knowing the characteristic impedance of the wire. And in a breadboard type system you won't know what the impedance is, no matter how hard you try. In this case, you'll simply end up twiddling with it until it just happens to work.
Pay attention to the signal return paths and loop currents. This is going to play the biggest part in making the system run fast. Of course, this is damn near impossible to do correctly with a breadboard, but those are the breaks. This is why people use power/gnd planes and 4+ layer PCB's.
I've ran PCIe (2.5 GHz) over wire-wrap-wire for about 5 inches. And I've ran PCIe over a "commercially available" wire for 12 inches. So you can get good performance from wire. It's all in how you use it.
A good breadboard can probably run faster than a bad 2-layer PCB.
Of course, most modern parts are in packages that require a PCB.
ASIC vs FPGA
A Field Programmable Gate Array can be seen as the prototyping stage of Application Specific Integrated Circuits: ASICs are very expensive to manufacture, and once it's made there is no going back (as the most expensive fixed cost is the masks [sort of manufacturing "stencil"] and their development). FPGAs are reprogrammable many times, however because of the fact that a generic array of gates is connected to accomplish your goal, it is not optimised like ASICs. Also, FPGAs are natively dynamic devices in that if you power it off, you loose not only the current state but also your configuration. Boards now exist though that add a FLASH chip and/or a microcontroller to load the configuration at startup so this tends to be a less important argument.
Both ASICs and FPGAs can be configured with Hardware Description Languages, and sometimes FPGAs are used for the end product. But generally ASICs kick in when the design is fixed.
FPGA vs microcontroller
As for the difference between a microcontroller and a FPGA, you can consider a microcontroller to be an ASIC which basically processes code in FLASH/ROM sequentially. You can make microcontrollers with FPGAs even if it's not optimised, but not the opposite. FPGAs are wired just like electronic circuits so you can have truly parallel circuits, not like in a microcontroller where the processor jumps from a piece of code to another to simulate good-enough parallelism. However because FPGAs have been designed for parallel tasks, it's not as easy to write sequential code as in a microcontroller.
For example, typically if you write in pseudocode "let C be A XOR B", on a FPGA that will be translated into "build a XOR gate with the lego bricks contained (lookup tables and latches), and connect A/B as inputs and C as output" which will be updated every clock cycle regardless of whether C is used or not. Whereas on a microcontroller that will be translated into "read instruction - it's a XOR of variables at address A and address B of RAM, result to store at address C. Load arithmetic logic units registers, then ask the ALU to do a XOR, then copy the output register at address C of RAM". On the user side though, both instructions were 1 line of code. If we were to do this, THEN something else, in HDL we would have to define what is called a Process to artificially do sequences - separate from the parallel code. Whereas in a microcontroller there is nothing to do. On the other hand, to get "parallelism" (tuning in and out really) out of a microcontroller, you would need to juggle with threads which is not trivial. Different ways of working, different purposes.
In summary:
ASIC vs FPGA: fixed, more expensive for small number of products (cheaper for high volumes), but more optimised.
ASIC vs microcontroller: certainly like comparing a tool with a
hammer.
FPGA vs microcontroller: not optimised for sequential code processing,
but can do truly parallel tasks very easily as well. Generally FPGAs are programmed in HDL, microcontrollers in C/Assembly
Whenever speed of parallel tasks is an issue, take an FPGA, evolve
your design and finally make it an ASIC if it's cheaper to you in the
long run (mass production). If sequential tasks are okay, take a microcontroller. I guess
you could do an even more application specific IC from this if it's
cheaper to you in the long run as well. The best solution will probably be a bit of both.
What a quick search after writing this gave me:

FPGA vs Microcontrollers, on this very forum
Best Answer
I think the differences can be boiled down into a few key points: First, boards that are designed for ASIC emulation can have several, very large FPGAs that usually provide mostly pure fabric logic resources (as opposed to DSP slices, hard IP cores, and transceivers) with lots of interconnections between them vs. "normal" dev boards which usually have just one mid-range FPGA. Second, boards intended for ASIC emulation usually don't have much in the way of peripherals, usually just broken out IO pins and serializers and possibly some memory modules, unlike normal FPGA dev boards that usually provide a 'kitchen sink' of various peripherals. ASIC emulation boards will also contain dedicated nets for clocks, resets, and other global signals. The manufacturers of ASIC emulation boards may also provide various software packages and HDL IP that can aid in utilizing an ASIC emulator.
If your design fits on a single FPGA, then it doesn't make much difference what board you get so long as the FPGA is big enough and it has whatever connectivity you need. However, if it has to be segmented across several FPGAs, then you will probably want to get a board specifically intended for ASIC emulation.