Hallo!
Nein, das ist kein Denkfehler, da liegst du vollkommen richtig. Parallele Aufgaben sind für einen µC aber kein Problem, man löst sowas mit Interruptroutinen.
Such hier mal nach der Lib von Weja, der hat sowohl eine Zeitfunktion Gettime() als auch eine komfortable Funktion zum Auslesen des Encoders bereits eingebaut. Damit sollte die Berechnung der Geschwindigkeit mit ein paar Zeilen zu lösen sein.

Gruss Waste