If you are worried about cost, just run it on a subset of your servers. 10-20% of your servers should be enough to gather most information you need... unless you are using new relic as the only aggregator of server status/monitoring... and that should be heroku's job.
We were battling a specific type of Heroku error (H12) that really required all of our dyno's to be monitored. We turned NR off and went with a (much) less expensive service that ended up telling us exactly the information that we needed across our entire cluster of machines. Hopefully with this extra cash, NR can improve their service because I honestly wasn't that impressed. It didn't live up to the hype at all for me.