The data in question has apparently been discovered by law enforcement agents after analysing botnets. Unfortunately, the BSI didn't share more details about the investigation.
They said that it is not exactly clear how and when the botnet operators have collected these e-mail addresses and passwords, but that it's also possible that they have bought some of the data from other criminals.
Since emails are often used as default usernames for a variety of online accounts (email accounts, online shopping, social networks, ISPs), the agency has set up a website where users can enter their email address and have it checked against the list of compromised ones.
In case it has been, users are urged to use an AV solution to check their computers for malware, and then to immediately change all their online passwords - and not use the same one for multiple accounts.
The reason why the agency issued this warning is that half of the compromised accounts end in .de, which means that they more than likely belong to German citizens.
According to The Local, this theft of digital identities has been discovered in December 2013, but the agency took its time to notify potential victims because they needed it to set up the aforementioned website. Even so, the website was initially crashed by the initial avalanche of users.
So far, some 880,000+ users who used the site discovered that they have been affected.