Since it's been a while since you asked this question, I hope you found your answer already. If not,

At the top of the Shareaza Window, click Tools. Then select Shareaza Settings at the bottom of the window that pops up. Then click Library, and look for a button in the lower-middle part of the window that says, "Clear History Now."