A few comments...
Using only a response control is no good here as 99.99% of the work might go by without the server producing any response to the client. Allowing, in addition to a response control, an intermediate response message, would allow for progress updates when no responses are being produced. Also, the control should be allowed with result, to indicate for instance how far the server got before it gave up.
Nothing here should be specific to search operation. Progress is generally useful.
I think it would be good for the client, in requesting the information, give some indication of the frequency it wishes to be updated in (once per second? once per minute? once per hour). This would only a suggestion. The server must be allowed to return progress as convenient (and not overly burdensome) for it.
I'd recommend progress be measured using 0 to (2**31)-1 steps. This allows the server to hide the number of candidates from the client, and provides sufficient precision for most any application.
Lastly, I think this discussion should be moved to the IETF LDAPext list for comment from the LDAP standardization community.
-- Kurt