The ICO says that the fee must be based on the administrative cost of providing the information which seems consistent.

Since you're allowed to respond to the first request with a list of the types of information you control, you should be able to do this without a search (and without undue costs).