How can I interpret the readings of a USB voltage tester considering the input voltage is 5V and I am charging a 3.7V battery?
Learn this: Energy = Power x Time.

This device gives me the total current that went through over a period of time. Let's say after 2.5h of charging I get this:
IN: 5.22V TIME: 150min 0.835A

No, that's the average current, not the total. To try and &quot;total&quot; a current would be like trying to total your speed on a 150 minute journey. It makes no sense.

And that means over the duration of two hours and a half 835 mAh passed through at roughly 5V (that somewhat varies a bit).

No. The mAh is calculated, as suggested by the units, by mA x time (in hours). 835mA for 2.5 hours gives 2088mAh.

The device I am charging has a 3.7V battery with a total capacity of 800 mAh. And this is where it all gets confusing to me:
The total power that went through should be ~5 x 0.835 = 4.174W

No, you want to calculate the total energy that went in. That's power by time, so \$ E = VIt = 5 \times 0.835 \times 2.5 = 10.4 \text {Wh} \$

However, the 3.7V battery can take 3.7 x 0.8 = 2.96W = ~3W.

Again, W is power, Wh is energy. The battery can store 3 Wh during charge.

That's over 1 Watt difference that I don't know where it went.

No, it's 1 Wh difference.

Should I believe over a quarter (over 1W) of the power passed through is waste? Or is my math wrong?

That seems reasonable. Your battery will get warm during charging and the missing energy will have been give off as heat.