Mmm, I've found this really annoying too.
Not sure why the need to remove all the webpageicons from the bookmark list when you just want to clear the browsing history?
The way I deal with it is that once you've visited all your bookmarked sites to get the webpageicons (favicons) back, go to the Safari Folder in your user Library
~/Library/Safari
Then find the WebpageIcons.db file, and copy it to somewhere else on the hard drive (and keep it there).
Don't put in the Trash, as you'll have to load all the bookmarked websites again.
Then when you clear history, just copy back this old WebpageIcons.db file into the Safari Folder in your user Library. You may then need to quit and re-open Safari, but all the old bookmark favicons will be back.
Another slower way to get the favicons back is to go Show All Bookmarks in the Bookmarks menu, then highlight all the bookmarks, then double click to open all of them at once...
You may run in to a tab limit if you have too many though.