404 will not influence your positions on SERP, but you should fix soft 404 by sending proper response code.
How Google treats 404s and 410s, you can see at Matt Cutts video:
https://www.youtube.com/watch?v=xp5Nf8ANfOw
About your dropping, conduct an audit of your backlinks. Take a deep dive into whats going on out there: spammy websites, dead websites, over optimized anchor texts (you should check on site internal linking anchors too). After you find all the bad guys in your backlink profile, submit them to Google by using Disavow Tool.
If you got penalized by Algorithm Update, to recover will take some time:
- Panda Update - roll out once a month - you should improve website usability and content quality - it will take month or so to recover.
- Penguin Update - roll out at certain times of the year - reduce over-optimized content on site, improve anchors, clean up spammy backlinks - recovery will have to wait for next algorithm update, which occur every 2-4 months.
Extra note
Since you have more than 15K of pages, look for broken external links too. Large amount of broken external links can also lead to traffic drop.