There are so many things in this question that it is difficult to know where to start.
I am assuming that your FPGA logic is a SPI slave, not a master. If it is a master then you have a whole different set of issues which I'm going to avoid going into right now.
The simple direct answer to your question is that you need to sample an async signal at least two times the frequency of your signal. So if you have a 4 MHz clock then you need to sample it at 8 MHz or higher. Of course, nothing is simple or direct in this case.
You have things a little more difficult because you are not sampling one async signal, you are sampling three (CLK, CS, and MOSI). You also need to keep those three signals time-aligned with each other through the sampling process. And you have to spit out MISO in such a way as to not violate your setup/hold time at the master.
None of this is easy, but having a higher speed clock will make things much easier. How much higher depends on your code, and you didn't post your code. I think that I could write code to do it with an 8x clock, but that is just a guess. Honestly, however, I think this is the wrong approach.
SPI is a super simple interface, and it would be good if you kept it super simple. SPI has its own clock, and if you use it as a clock then everything becomes almost easy. Instead of changing clock domains on the serial SPI interface, change clock domains on the parallel data going in/out of your shift registers. If you look at those signals carefully you might even realize that you don't need to do anything special, or if you do then it's just a flip-flop per signal. Then you don't need to have your main clock be higher than your SPI clock. Your main clock could actually be slower!
I do this on my SPI FPGA/CPLD interfaces and I have no problems running SPI at 30+ MHz, with or without a second clock domain.
The core clock of the CPU isn't received directly from the motherboard. That clock is usually much slower (often by a factor of 10 or more) than the internal frequency of the CPU. Instead, the clock signal from the motherboard is used as the reference frequency for a higher frequency phase locked loop controlled oscillator inside the CPU. The generated clock runs at some multiple of the reference clock, and that multiple can be changed by setting certain registers in the CPU. The actual generation of the clock is done purely in hardware.
To reduce power even further, the CPU also signals to the voltage regulator supplying its core voltage to run at a lower set point. At lower frequencies the CPU can run at a lower voltage without malfunctioning, and because power consumption is proportional to the square of the voltage, even a small reduction in voltage can save a large amount of power.
The voltage and frequency scaling is done by hardware, but the decision to run in a low power mode is made by software (the OS). How the OS determines the optimal mode to run in is a separate, messier, problem, but it likely comes down to mostly what %time has the system been idle lately. Mostly idle, lower the frequency. Mostly busy, raise the frequency. Once the OS decides the frequency to run at, it's just a matter of setting a register.
Reference: "Enhanced Intel SpeedStep Technology for the Intel Pentium M Processor"
Best Answer
Actually crystal oscillators can easily go up to 10's of MHz. Above that in most cases a PLL (Phase Locked Loop) is used, which is an oscillator that is not very accurate in itself, but can be tuned (its frequency can be adjusted somewhat). The frequency of this high-frequency oscillator is divided by a suitable factor (dividing a signal by a power of 2 is easy and totally accurate), and then compared to a let's say a 10 MHz oscillator. The comparison is used to adjust the high-frequency oscillator. Thus a high frequency is made with (almost) the accuracy of the lower frequency crystal oscillator.
In most cases, the circuitry to do all this is built into the processor chip. This is so it can be configured under software control, and routing such a high-frequency signal between chips is a nightmare.