I think there are a couple of different ways to look at this.
Deduplication is a technical detail that's irrelevant here
While the data may be deduplicated on a technical level, the files remain logically distinct.
If users 1 and 2 upload identical files, and then one user edits or deletes their file, this will not affect the other user's data.
Users cannot tell whether their files are duplicates of someone else. From the user's perspective, it makes no difference whether or not the storage uses deduplication, except perhaps via the cost of the service.
Because there is no user-perceptible difference, it would be difficult to interpret some GDPR significance into this scenario.
Whose personal data is it anyway?
Personal data is any information that relates to an identifiable data subject. The files here are likely to be their uploader's personal data. Thus, the uploaders would also have a right to have their uploaded files erased. In case of deduplicated storage, this would affect their logical copy.
The contents of the uploaded files might also be personal data relating to a third party. Then that third party might have a right to get the file contents erased. But this right must be invoked with the data controller for that processing activity, which might be company A, company B, or the uploaders, depending on context. Which leads us to the next aspect:
Company A is not responsible for handling erasures
From your description, it sounds like company A is a data processor providing services on behalf of company B. In turn, B might be a processor acting on behalf of the uploaders. In any case, it seems that A would not be the data controller for these processing activities. Data subject rights like erasure must be invoked against the controller, as only the controller can understand whether such a request should be granted. The right to erasure is not absolute, and depends a lot on why that data is being processed. In particular:
Personal data need not be erased if it is still necessary
For example, a person might very well be the data subject of some of these files, and might then ask for erasure. But if the files are being stored because they are going to be needed as evidence in legal proceedings, the data subject can't use this GDPR right to destroy evidence. The data controller would be allowed to refuse a request in such cases.
It could now happen that two different users of this deduplicated storage are storing the same file, but for entirely different purposes. Blanket deletion of all copies of a file could be quite problematic. Note that deletion is also a "processing activity" and needs a legal basis under the GDPR. Unexpected data loss could be a data breach. One user's erasure could be another user's reportable data breach incident.
Thus, I would strongly expect such requests to be handled on a logical file level, not on the deduplicated storage level.
Caveat: public access and cloned files
If the (logical) file is made available to the public who can then clone or copy this file, and if the "original" is taken down due to an erasure request (or copyright takedown notice), it might be appropriate to remove logical clones as well. Again, this might not involve deleting the contents on the deduplicated storage level, but it might affect other users' copies.
In a GDPR context, the grounds for this would be the Art 17(2) right to be forgotten:
Where the controller has made the personal data public and is obliged pursuant to paragraph 1 to erase the personal data, the controller, taking account of available technology and the cost of implementation, shall take reasonable steps, including technical measures, to inform controllers which are processing the personal data that the data subject has requested the erasure by such controllers of any links to, or copy or replication of, those personal data.
But this depends crucially on who those other controllers are. If A is the sole controller, the logical files could probably be deleted directly. If B or the end users are controllers, it could be more appropriate to forward the erasure request to them.