I believe it depends upon which SharePoint version you are using. Your question tells me that you might be using SharePoint 2007, since you emphasise on the 2000 items limit. This limit in the list is just for retrieving the items in a single view, but you can have millions of items as long as you don't display more than 2000 items in a single view.
You can view the msdn article for the entire limits in SharePoint 2007- http://technet.microsoft.com/en-us/library/cc287790.aspx
Deleting a whole list with just 4000 items should not have any impact. You should be able to do that through browser with a minimum delay. Deleting the list items individually through Powershell is not advised as it could impact your farm depending on the method and code you are implementing in Powershell.
I would also recommend to duplicate the site in a test environment to make sure that nothing is affected in your site when the whole list is deleted. Please also find other articles recommending similar situations - How may document libraries are recommended for a site?