Shorturl with almost one million of rows

This is indeed normal behaviour. If you've sent 80k mails with 12links in each mail you'll get 960k shorturl's...
I currently don't know if this could become a problem...

Well, the problem is that my database who had a slow and steady growth, in a few weeks tripled in size, hindering the process of backup and making it very slow.
Is it really necessary to keep all these links?
It would be possible to choose to not use this table?

The data is the basis to making the links actually work. So no, you can't just not use that table.
The D7 version will be completely overhauled on this front and will most likely produce much much less records.
But I will not be putting anymore time in the D6 version myself to handle issues like this. (strictly bugfixes for me) If you want to tackle this I would be more then happy to apply your patch. But I'm afraid that this simply can't be fixed without some major work...

It would be possible to create a hook_cron (like dblog module) to delete such records over 30 days?
Would this give some other side effect or just the statistics before 30 days would be lost?

Statistics will keep on working, but all the links in your newsletters will be broken.

Well, this is sad.
Although statistics are interesting, now I'll be stuck with a massive database that will double in size every month ...
f there was a way to reduce it, but as you said, you just will stir it in D7 ... it's a shame ....

You could delete links from old newsletters. I think it's safe to assume that in most cases users won't click on links in newsletters older then a few weeks.
But you'd have to keep track of wich links to delete by hand...

I dont understand why there is short URL for each email? If I have one NLetter with 12 links and send it to 100 000 people, that should still be 12 links? Why do we need to have so many links?

This is beacause in the D6 version every link is unique to be able to track individual clicks for every user. This was done with RC4 encryption resulting in enormously long URL's. (something I inherited from the previous maintainer) I therefore pushed shorturl onto the module to make these URL's shorter and less "spammy". But the shorturl fix had the very negative side effect of storing everything in the database. (maybe you could try and disable this)

In the current D7 version this sytem has been thrown out and replaced by #1775364: Url shortener and encryption. In short: the URL is now constructed with 2 ID's. (1 for the user and 1 for the url) The pieces are just the plain ID's. (so only a list of all links is stored in the database)
Optionally these ID's can be encrypted by the provided encryption submodule (same algorithm as shorturl but without the need to store anything in database) or you could plugin your own encryption engine.

Maybe this part of "able to track individual clicks for every user" should be as separate submodule. It is very powerful and give very precise data what specific user did, but I would say most user won't need that as they want to see just sent/open rate of NL.

I'll reopen this issue.

So there are 2 possible solutions for now:
1) Make shorturl not store everything in database
2) Disable tracking on a per user base

I've looked at this again in detail now.

It seems a very big task to try and do something about this and I'm not willing to put much effort in the D6 release anymore. So if anyone else wants to patch this I will commit it.

For now you'll just have to stick to a manual cleanup from time to time.

If you disable simplenews_statistics but want to keep the short URLs working, you need to keep the shorturl module activated. To save space you can use myisampack on the shorturl_link table. It will become read-only but you will save a lot of space.

If you want to keep using simplenews_statistics, check out #2205731: Decrypt short URLs after N days.