Hello,
well, first of all it is important to find our where from those "millions" of URLs are being generated from:
- what component
- vhaw view or what parameters are causing this
You should be able to find this out using component filters. (and see which on them is responsible for most of your stored URLs)
It may occur where there does not exists suitable extension for some add-on component. Very often, similar problems are caused by components having "infite" number of URLs, such as calendars, where crawlers keep following "next day" link and that generates stil new and new URLs.
You can surely delete all URLs where impressions = 0. The problem with memory limit being reached can be either solved by increasing it temporarily or by deleting the URLs at the DB level using a SQL query in tool such as PhpMyAdmin.