There are several ways "Mr. Evil" can get your login details. The most likely possibilities are:
1)
Malware on your PC "watches" you type your eBay login details and sends them to Mr. E.
In this case, run anti-malware scans with
Malwarebytes and
adwCleaner.
2)
Another of your accounts has been hacked (as PCBaby suggests).
In this case, you can (if you wish) enter your email address into
haveibeenpwned.com and it will search to see if that address appears on any lists of known stolen login details.
3)
A phishing attempt.
The "from" address in an email can be changed to whatever you want it to be. So anyone can send an email from "ebay.com" and make it look completely legitimate... apart from one thing. The links in it can take you to a fake eBay page. If you log in to this fake site, it will probably send your login details to Mr. E, and then pass the login details to eBay so you get logged in to the real site as if nothing happened.
So... never click links in emails unless you're 100% sure they're legit.
4) Unlikely, but if you are using wifi and have a modestly skilled Mr. E within wifi range, it's
theoretically possible he could have set up a
"man-in-the-middle" attack and "fooling" your computer into connecting to that, rather than your own. That way your Internet traffic can be intercepted. Login details will still be encrypted via HTTPS, but Mr. E could steal login tokens (cookies) that can be used log in as you.
One way to counter "man-in-the-middle" attacks is to use a VPN, but all that does is make the VPN owner the "man in the middle". If the VPN owner is Mr. E, then you're potentially giving away all your sensitive data, and maybe even paying for the privilege. For that reason, it might be worth looking at VPN services in countries with high accountability and privacy laws. VPNs in these countries are not always popular with people online who are using VPNs to circumvent local laws (on copyright, etc.) as they are not transmitting sensitive data, and are more worried about the authorities seeing what they're doing than Mr. E. So read the reviews carefully... What's best for one person isn't the best for all. Some VPNs are
very shady... and you've got to wonder how the free ones are being paid for...
Personally, I don't think a VPN is worth it. I'd never use one to transmit important login data or credit card details... But I operate on near-paranoid levels of security.
One of THE MOST important passwords is the one for your email account. If Mr. E has access to that, he can lock you out of your email, and change the passwords for other accounts you have that use that email address. So, (aside from financial institutions) if there's one password that needs to be long, non-guessable, and unique, it's that for your email account.