You're both right in a way, depending on whether you're comparing force or power required. In the equations I've seen, rolling resistance (force) is usually considered as a constant factor x weight, independent of speed. But the power needed to "overcome" rolling resistance is linear with speed, because power is always force x velocity.
EG, at a typical coefficient of rolling resistance (CRR) of .006, and a total weight (bike plus rider) of 90 kg, drag force due to tires would be .006 x 90 x 9.8 = 5.3 newtons Since power is just force x velocity, at a speed of say 10 m/sec, power needed for RR is 53 n-m/sec, or 53 watts. Halving the speed would of course halve the watts.
If you think about gearing, it's easy to see why the power needed to overcome a constant drag doubles when the speed doubles. Even though the force needed at the rear wheel doesn't change, we have to either pedal twice as fast at the same force, or use "twice" the gear at the same cadence, meaning we have to push twice as hard on the pedals. Sadly, either way, power output of the rider has to double