Google Music now has a trash page that includes all the songs you've deleted. You can find the page by clicking the "options" icon and selecting "Music trash" from the menu. The songs are permanently deleted after 28 days (why not 30 days like in Gmail?), but you can also manually do that. There's also an "undelete" button for restoring music files.
It's interesting to notice that the deleted music files are no longer synced with Google Music Manager. As Google explains, "once you permanently delete [a song], the content and related data (e.g., stored play counts) will be disassociated from your account. There may be some delay before our systems fully process your removal request. In addition, if this content was purchased from Google Play, the only way to retrieve it is to repurchase the content."