The module will continue to be listed on the /admin/modules page as long as Drupal detects it on your filesystem within /sites/all/modules, /sites/default/modules, or another folder under /sites if you're running a multi-site setup. Just because the module is listed there doesn't mean it is enabled and running on the site.
Uninstalling modules is usually done the way you described it in the first line of your post. You go to /admin/modules to disable modules, then onto /admin/modules/uninstall to uninstall them. If the developer of the module did it correctly, you shouldn't have to do anything more than that. You will still see it listed in the modules page because it is still on your filesystem
I wouldn't recommend manually deleting anything out of the database unless you know exactly what it is that you're doing. You could mess things up When you disable and uninstall modules through the Drupal interface (or Drush), there are certain hook functions that get called which should remove data from the database.
What I would do is first is locate the module folder containing MailChimp. Ensure that you only have it in one place. If you had the module in different folders and only delete one, it will still be listed on the admin/modules page.
If you don't see it in those folders, re-install it. Then properly disable and uninstall it again the way you described WITHOUT touching the database yourself. This will probably undo any damage you could have caused in the database and ensure that the data in the database is properly cleared out. Afterwards, delete the module folder from the filesystem and it should be gone.