I've cycled fairly extensively (~5000 miles) through western Europe and Scandinavia so should be give you some fairly good advice. I've not been through eastern Europe. Feel free to ask any questions.
Edit: I think your goals are easily reasonable, Europe isn't that big so ~10,000 miles should allow you to cover most of it. it's only about 2000 miles from Istanbul to London by bike.
First of all definitely go for panniers, you probably won't be able to carry everything you need in a pack and it would be very uncomfortable. I'd recommend getting a hybrid bike and fit schwable Marathon plus tyres on them (you'll never get a puncture with them), also ideally train on that bike as you'll get used to it's riding style and it will make the trip easier. make sure you buy lots of food on Saturdays as ALL shops are closed on Sundays in continental Europe, including most supermarkets. learn to love supermarkets such as Aldi and Lidel.
You'll definitely need a tent, aim to buy one that is as lightweight as possible and that can be put up and down in the rain without getting the inside wet. If you go to Norway this will be especially useful. you probably need some kind of cooking facilities unless you want to eat out every day which will be EXTREMELY expensive. I'd recommend some kind of camping stove, campingaz is sold fairly widely throughout Europe.
EDIT: considering your budget maybe you wont need this... $20,000 should go a long way if you're sensible. (except in Scandinavia where it'll last you... not very long, also you may not be able to find accommodation, especially in the remote north as towns can be more than a days ride apart). even so it's good to have a backup.
Norway is beautiful but it rains a hell of a lot, I was there in the summer a few years back. We started off cycling in Tromso in August and it was 5°C outside and raining (it rained every day). Admittedly that was right up in the North but you get the idea.
Edit 2: if you're in Norway and someone says your destination is but 3 miles away, they could either be using the normal mile or the Norwegian mile, 1 Norwegian mile is roughly 8 normal miles, I found this out the hard way.
Make sure your wet weather gear is sufficient that you can stand under a shower for a few minutes and be completely dry underneath.
MAKE SURE YOUR BIKE SEAT IS AT THE RIGHT HEIGHT, very important as if it's wrong you could damage your knees badly due to extra pressure on them. if you're seat is too high the back of your knees will start to hurt, if it's too low the front. If at any point your knees start hurting alter your seat height immediately as it will only get worse until you can barely walk. this will happen over the course of a few days, not instantly.
As for distance, I normally manage about 1000 miles every two weeks but that's fairly fast going with no stops.
Your running fitness is amazing, but it won't help your cycling at all. If you want to train for it, cycle.
Do a week practice run somewhere just to make sure all your equipment works. but also likely to discard equipment you don't need without having to throw it away.
And finally make sure everything you have as lightweight as possible, this is very important for when you're going up hills.
Final edit: this website is really good for kit lists and planning ect. http://www.adventure-cycling-guide.co.uk/