It depends entirely on what sort of malware it is, and what effect it is having.
If the malware is preventing search engine bots from accessing the site, then it will of course affect your site's search performance. In the case of Google, if their bot detects the presence of malware but is still able to access the site, it will continue to show the page in its search results, but it will display a warning saying that it appears to be infected.
As for how to remove the malware, it's impossible to answer that without having more details about what the malware is. Have you tried contacting the support people at your hosting company?