Labels do not consume any significant space.
I understand that this version of TFS has added the option to output
builds to the TFS server, in an un-version controlled location
(http://nakedalm.com/new-un-versioned-repository-in-tfs-2012/)
This came from VSOnline, where your output could be stored back into source control, this is an available option in TFS2013 but only if you choose the Copy Build Ouput to Server option in the build defaults. Use a network share instead to store your build outputs, if you believe this is consuming too much space.
When you delete a build through the retention policy, most artefacts of the build will be deleted for example the drop folder, and you will no longer be able to see the build in the build screen, however this is only a logical delete and the records remain in the database but are flagged with a delete flag.
The Destroy command will physically delete the build from the system, it will be completely gone and all records will be removed from the DB, please bear in mind that TFS may not recover the space straight away, the TFSJob Agent will recover the space during its normal running process so you may not see the space recovered for 24 hrs +.
You can check the size of the test attachments table as you may find that your space is being consumed by test libraries etc that are being stored.
installing TFS Power tools will install the test attachement cleaner tool and running this will show you whether it is the test attachments that are consuming space. it has instructions for how to clean up the table and how to run a scheduled job to keep on top of the housekeeping
TFSBUILD Destroy example
this will destroy all builds between 5/5/14 and 20/5/14 that have been deleted
tfsbuild destroy /collection:http://TFSServer:8080/tfs/TPC /dateRange:05/05/2014~20/05/2014 /buildDefinition:POC\zzz_DBSample
Microsoft (R) TfsBuild Version 12.0.0.0
for Microsoft Visual Studio v12.0
Copyright (c) Microsoft Corporation. All rights reserved.
Destroy build record for DEV_DBSample_1.0.14128.1 permanently? (Yes/No/All) y
Destroying DEV_DBSample_1.0.14128.1... Done
Destroy build record for DEV_DBSample_1.0.14128.2 permanently? (Yes/No/All) a
Destroying DEV_DBSample_1.0.14128.2... Done
Destroying DEV_DBSample_1.0.14128.3... Done
Destroying DEV_DBSample_1.0.14128.4... Done
Destroying DEV_DBSample_1.0.14128.5... Done
Destroying DEV_DBSample_1.0.14129.1... Done
Destroying DEV_DBSample_1.0.14129.2... Done
Destroying DEV_DBSample_1.0.14129.3... Done
Destroying DEV_DBSample_1.0.14134.1... Done
Destroying DEV_DBSample_1.0.14134.2... Done
Destroying DEV_DBSample_1.0.14135.1... Done
Destroying DEV_DBSample_1.0.14135.2... Done
note how the build definition name has changed since the builds were created and TFS still finds the correct records