The answer by Tim is super, and still relevant in 2017, but omits one important thing: PRIVACY.
you have to trust the company (in this case Sofort AG), as they could also just take all your money if they wanted to
Risk exists, but is probably low - or their whole business model would collapse. The risk provides a serious incentive to take security seriously.
I actually asked my bank (BNP Fortis Paribas) about Sofort (now Klarna) with the same comments as OP, and they did not discourage me from using Sofort, nor scorn me for sharing my login details... instead encouraging me to contact Sofort with my question instead (much like the reply this customer received). Tim's statements explain well enough why.
But you also have to trust Sofort to take your PRIVACY seriously.
Sofort effectively have access to your bank balances on all your accounts, all transactions that you made - the same ones that are visibile in your bank's online portal. This appears to be depending on the setup they have with the various banks; if there is no API from the bank, then their Data Protection policy states:
"Alternatively, our system will automatically call up the data via the
user interface of your online banking service, much in the same way as
if you logged on yourself".
I.e. they [can] know what you earn, where you spend your money, what your cash burn rate is, what your savings or investments are.
I'm sure that information is HUGELY valuable.
If you perform 1 Sofort transaction every 6 months, for my bank at least, they could assemble a continuous transaction history for every customer.
The only thing going for them IMHO is German privacy laws are among the strictest in the world...
We will not store any personal data beyond that, in particular, no
account balance, transaction data, overdraft limits, account lists,
online banking login passwords (such as personal identification
number) or confirmation codes such as transaction authentication
Thing is though, it's easy enough to audit whether your money has been stolen. It's quite something else to verify whether the company is complying with its promise not to collect this data. So it's all about trust. Don't trust them? Spend a few €€€ more, and use another payment provider.