Paypal is safe. When you use Paypal, your credit card/banking information is not exposed/sent to a merchant; they simply tell Paypal how much to charge you and Paypal handles everything behind the scenes so all Newegg gets is a token. In fact, as a matter of good security, I always use Paypal whenever I have the option to because Paypal is infinitely more secure than some random small time e-commerce website with limited resources for IT security.
I lean toward agreement with damicatz on this. PayPal acts as a trustworthy proxy and they have never ever screwed me on anything.
In fact, PayPal is even being accepted by some retail merchants like Home Depot if I remember correctly. You don't even need a card with you.