A storage system in one embodiment comprises a plurality of storage devices and an associated storage controller. The storage controller is configured to identify a dataset to be scanned to generate a capacity release estimate for prospective deletion of that dataset, to designate a content-based signature prefix to be utilized in the scan, and to scan logical address mapping information for the dataset to identify one or more pages of the dataset that have the designated content-based signature prefix. The scanning further comprises, for each such identified page, determining a reference count of the page, and responsive to the reference count of the page having a particular value, determining a compressibility measure for the page. The storage controller generates the capacity release estimate for prospective deletion of the dataset based at least in part on the one or more page compressibility measures determined as part of the scan.