Probably best to get help from your host provider (btw which hosting provider is this?), but you could check (as many Linux servers have all the php versions in there): ls /usr/bin/php*
to see perhaps what versions of PHP are there. Perhaps you will see something like /usr/bin/php56. If so, if you run /usr/bin/php56 -v what do you get? If you find a (cgi) version of php that is 5.6 that is good, if it is a (fcgi) version then it isn't any help. Let me know if that helps. Probably your host did not change the command line php when they upgraded to php 5.6.
The "No route found. " is also interesting. Did rebuilding the index work in the past via the admin panel? Maybe it is not a database size issue but some "bad" content that has been recently added that causes the indexing to fail (just a guess though). If you index via the control panel with the logging option on, you can see the last lines of the log file to see what the last item it tried to index before failing. You can then manually look at that piece of content to see if it has anything special/weird that might cause an issue (some kind of redirection to a non existent page perhaps, which is what No route found would suggest).