I don't know how he came up with it, but I did some slides giving some geometric intuition about why it's the natural choice:

http://slesinsky.org/brian/misc/eulers_identity.html