Increase of 404 Crawl Errors in Webmaster Tools

Here’s a guess: it’s actually your theme. Your theme is probably using pagination that doesn’t understand Relevanssi, and it’s showing the pagination based on WP default search, which doesn’t always have the same number of results pages as a Relevanssi search, thus your pagination is linking to non-existing pages.

If you take a look at a search term that’s causing the problem, does the pagination go one page too far? How many results are found, how many pages there should be, how many pages there are in the pagination?