The data controller is responsible for GDPR compliance. When the controller engages a data processor, the data controller must ensure that the data controller can fulfil their obligations. For example, the data controller should ensure that they can delete personal data processed by the data processor.
How the controller and processor sort this out is up to them. It would certainly be permissible for the processor to charge a fee for the services they provide, even if that service is strictly necessary for the controller to be compliant.
In your scenario, the controller is not fully compliant because the controller hasn't prepared properly for a data subject request. The controller should never have engaged the processor without checking how data can be deleted. Now, the controller wishes to obtain additional services from their processor. The two parties will then negotiate and enter a contract for these services. The parties are free to negotiate the terms of this contract, including seemingly unreasonable payments. The usual rules on contracts in the relevant jurisdiction apply of course, e.g. a contract typically requires offer and acceptance so the processor can't just demand a made-up payment after already having provided services – but they may be able to demand a reasonable payment even if this wasn't agreed upon explicitly.
While it is generally free for two parties to decide whether they enter into a contract, there is an additional constraint if the processor is under contract as a data processor per Art 28 GDPR (as they should be): in point (3)(e), it is required that the processor, “taking into account the nature of the processing, assists the controller by appropriate technical and organisational measures, insofar as this is possible, for the fulfilment of the controller’s obligation to respond to requests for exercising the data subject’s rights laid down in Chapter III”.
Then, the processor must provide assistance e.g. by entering into a contract for providing services. A court might also find that this assistance must be offered under reasonable (non-extortionate) terms. However, there is absolutely nothing here to indicate that the assistance would have to be rendered at cost or even for free.