Koepel:
"should" be okay. But the more I keep staring at it, the more it gives me a funny feeling. I prefer to tell the compiler what to do, instead of hoping that the calculation will not go wrong by using 16-bit integers combined with unsigned long.
The "(now - lastTime)" is about 1 second or a little more. By doing "30000/1000" the result is 30 and you are losing some accuracy.
The line "unsigned long now = millis();" grabs millis() at that moment. You use that moment to calculate the revolution. But when you use the variable 'revolutions', you use that variable at a later moment. Meanwhile an interrupt could have happened. You also lose some accuracy there.
The 'revolutions' and 'revolutions2' are two bytes in a ATmega32U4, but the microcontroller is a 8-bit microcontroller. That means when you use 'revolutions' in the loop(), an interrupt might occur while the 'revolutions' is only half read or half written. That interrupt might update the 'revolutions' and you could have something wrong. The chance that this will happens is almost never, but perhaps you can make a copy of 'revolutions' with the interrupts turned off.
Yes, this is clear. Just wanted to create a quick example. I completely agree that it is better to tell the compiler what to do 
Tried changing these things but it did not have any effect.
Koepel:
I don't think these minor software problems are the cause of the wrong readings.
I think you have a hardware problem.
Why pin 0 and 1 are different from pin 7 is a mystery to me. But with a bad GND anything is possible.
The ATmega32U4 has low level digital inputs. It recognises a HIGH level at a lower voltage and the signal must be extra low for a valid LOW level.
Perhaps the GND is not well connected, or the signal is noisy.
Are you sure the GND of the signal is connected properly ?
Can you add a RC-filter for both rpm signals ? Depending on the voltage levels of the rpm signal, a RC-filter and a transistor might be better to be sure that the ATmega32U4 gets a good LOW level.
When the rpm is maximum 4000 (per minute), that is 67Hz. You could try a resistor of 4k7 or 10k with 100nF.
Do you have a Arduino Uno, to compare the results ? The Arduino Uno has other voltage levels for a digital LOW and HIGH at a digital input pin.
The best way to find the problem is to measure the rpm signal. Do you have a oscilloscope ?
I think it is a good idea to try a RC-filter.
Fall back to something that is known to work. Could you try the FreqMeasure ? Make a new sketch and use the FreqMeasure by Paul Stoffregen. It is in the Library Manager (in the Arduino IDE). It uses pin 13.
Both fans and the board are connected directly to the power supply and using the same ground. Could of course be some ripple effect but my assumption is that it should affect both inputs in the same way. Also tried using pin 2 with the same effect as for pin 0 and 1.
At the moment I don't have a spare board (I have a Mega 2560 but it is currently tied up in my autonomous RC vehicle and somewhat difficult to disassemble). Don't have any capacitors at the moment so cannot add an RC filter and no oscilloscope. 
Since FreqMeasure uses pin 13 I don't think I can use it with the Pro Micro board since as far as I understand it doesn't have a pin 13.
Thanks a lot for the support! I will look into getting another board to verify with, might need one with more connections anyway to run additional fans, sensors, etc.
Update
While writing this I tested with different values for analogWrite and observed that when I set it to 0 or 255 then everything works correct. It also seemed to be connected to analogWrite on pin6 being set to those values.
But then my board stopped working. I cannot connect to it and it does not show up as a COM port anymore. So it might have been a hardware problem with the board or something might have got short circuited while I was trying different connections. So now I have to get a new board anyway.
I want to thank you for your input and might post again if I have any problems in the future, it feels like this is a good place to get help.