Being that someone I know entered Turkey on their passport and exited on their ID card hassle-free (claiming to have lost the entry form, and getting a new one with only an exit stamp) you should be fine. Turkey, unlike most EU countries, records entries and exits electronically.
If you want it confirmed, though, you can always go to the airport and ask to speak to the border police. The higher-ranking officials normally speak some English.
You will not need a new E-Visa seeing as they're mainly a prerequisite for entry. Once you got in, you were granted a stay of 90 days, which isn't invalidated just because the travel document tied to it got lost.