Hi there,
Robotics is one of my hobbies, and I have had similar experiences to you trying to make an affordable DC motor based platform with encoders. I used to enter micromouse competitions, and would like to release an open source cheap robot platform design at some point. Anyway...
Your signal swing looks almost sine like, and is very small in amplitude. How have you set your photo diodes up? Got a schematic?
Also you maybe able to get decent resolution from encoders at the wheels if you use what is known as a quadrature encoder. You can scavenge quadrature encoders (LED and Sensor) and their matching encoder discs from old mechanical ball mice. Two sensors are placed 90 degrees out of the phase (note two "sensors"/photodiodes are placed in the same physical package), which allows you to not only to detection direction (by seeing what phase leads), but also allows for a x4 improvement in resolution as you now have 4 edges to detect in one encoder "click" (2 positive going edges and 2 negative going edges) so to speak. Decoding the quadrature signals reliably into pulses and direction will add a bit of complexity to your robot mind...
Another thing to consider is something I have seen done in the past. Disassemble the motor, and drill a hole in the casing away from the permanent magnets but such that you could see the motor poles. Paint the rotor pole ends with white paint, and then direct a reflectance sensor through the holes to detect the poles moving past and count them.
Most DC motors like those have 3 poles, so you would have 3 ppr at the motor, but those gearboxes typically have substantial reduction ratios > 100:1 so you would still have respectable resolution at the wheel, i.e. >= 300 ppr.
BTW You have measured the frequency over the period of two cycles there, so double your 38 Hz and RPM.