If the server can give a rough estimate of how long a job will take, then I would return that estimate in the first response (the one indicating that the job was received/accepted). The client can then wait at least that time before it starts polling for results.
To avoid flooding a server with unsuccessful polling requests, you might also use a scheme that is often used to send retries over an unreliable protocol: After sending a request, wait a time T before sending a retry. After sending a retry, double the waiting time, until a maximum T2. After success, the waiting time gets reset to its default (minimum) value T1. You could, for example, use the values T1 = 250ms and T2 = 16s
As an example, here is what the polling would look like for a job that is estimated at 2 minutes and runs a little late (network latency ignored):
Time Action/Reply
---- ------------
0:00.000 Start job. Server responds with a duration of 2:00 minutes
2:00.000 Polling starts. Server responds job still running
2:00.250 First retry. Job still running
2:00.750 Second retry. Job still running
2:01.429 Job finishes
2:01.750 Third retry. Job reported as done.
As you can see, there is some latency in reporting that the job is done, but what is a delay of a few hundred milliseconds if you were already waiting 2 minutes for the job to complete?