As stated in the question: When the minimum tick size in the US was decreased, the payments for order flow also decreased.
Why is this the case?
Assume the minimum tick size is 12.5 ct and further assume the spread is evenly set around the midpoint:
|-- 6.25 ct 12.5 ct ---| |-- 6.25 ct
If the actual (equilibrium) spread was 5 ct:
|-- 2.5 ct 5 ct ------| |-- 2.5 ct
The market maker makes 6.25 ct per transaction in the 12.5 ct case. Hence, if the minimal spread was 12.5 ct he would be willing to pay up to 3.75 ct (=6.25-2.5) for each transaction.
If you reduce the minmum tick size, the market maker will pay less for the order stream because there is less money to make.