Storage calculations in Salesforce are not quite as you might expect. Each Lead counts as 2KB regardless of how many custom fields there are or whether they contain any data.
http://help.salesforce.com/HTViewHelpDoc?id=admin_monitorresources.htm&language=en_US
As evidences in 'Personal Edition' (10,000 records = 20MB) this may come as a surprise! Even an object with 1MB of data in a bunch of text areas counts as just 2KB towards your storage limits. Some objects are 'heavier' than others (eg Campaign at 8KB) but to reclaim space you need to clean records vertically as opposed to horizontally.