I guess that depends on the fan and what you want to monitor? Do you want to monitor motor shaft speed? If it's belt drive, do you want to measure driven shaft speed? Do you not really care, you just need to know if the motor starts running slower than a "calibrated speed"?
A 18mm inductive or magnetic prox would work fine. Possibly even a polarized retroreflective. With the former, you would need to detect metal or a magnet passing. With the latter, you would need to see a break in the beam.
If it's a belt drive fan with "spoke" type sheaves, you could mount a prox behind the sheave and it would detect a spoke every time it passes, giving you a pulse to count. If you do some math with it, you could determine the true RPM of the fan or motor shaft. Even a cheap $70 Click PLC with a $30 prox sensor could do that with just a few rungs of code.
Depending on the spoke or fan blade configuration (and this is assuming a permanently mounted fan), you could shoot the beam through the fan to a reflector and count pulses that way. That would depend on blades on the fan, fan speed, blade width, etc etc.
Just for kicks and grins (and because I'm in the middle of building a panel and I had a retroreflective sensor sitting here with a 20" 5-blade fan), I did a quick test.
Over 10 seconds with the fan on high, I registered 792 pulses. Over the same time period on low, I registered 592 pulses. This was shooting a cheap visible red retroreflective sensor through a box fan to a reflector on the other side of the fan housing and doing it handheld. The fan has zero specs on it, so I don't know how many rpm it is supposed to be turning, but at the very least it gives a quantifiable number that you can calibrate against. I know that if I'm getting less than say, 52 pulses per second, something is not quite right.