6000 rev / min = 100 rev / second
100 revs / sec * 10 pulses / rev = 1000 pulses / second or 1mS between pulses.
You can't do it with millis() because at 4000-6000 RPM it will always read 0 or 1 millisecond since the last pulse time. micros() will work better. Alternatively you can measure the time for 100 pulses or count the number of pulses in 100mS (for example).
1 mS is enough time to read the state of three pins and check the time, but it depends on what you are doing with the information and how long it takes to process it. If the application can monitor speed for a period of time, and then do something with it (while not monitoring speed) then it should not be a problem. If you have to monitor speed continuously, then it depends on what else the system is doing.