Deleted Messages still take space on iCloud
You might have a backup from one of your old devices still saved in your iCloud account. From an iOS device, try to check by going to Settings>iCloud>Manage Storage>Backups. This page will list the backups and associated device with the backup. On my account, the total size matches the total size of the Backups listed in Safari.