To be clear, I have a pool of 800K theoretical UAs derived from the mechanism I use to generate them, not 800K clients.

Regarding costs, I really have no idea. It depends on how rapidly you cycle the UA, and how fast whatever you're scraping is.