Something that also may be useful is AccurateTiming from GeneralUtilities`.
Needs["GeneralUtilities`"]
?AccurateTiming
AccurateTiming[body ] evaluates body enough times to give an accurate time profile, giving the average time taken it takes to execute.
Now, this does not take care of your problem directly, but it can be useful in getting a sense of how long something takes that is of variable clock time. You can do this by having AccurateTiming do a timing of an AbsoluteTime call. Here is a trivial example:
In[45]:= First@Timing[Pause[.1];]
Out[45]= 0.004147
In[46]:= First@AbsoluteTiming[Pause[.1];]
Out[46]= 0.101146
In[47]:= AccurateTiming[First@AbsoluteTiming[Pause[.1];]]
Out[47]= 0.100612
And here is something more like a case where the function that is being called an take a variable amount of time:
In[52]:= Options[AccurateTiming]
Out[52]= {TimeConstraint -> 1., MaxIterations -> 1024}
In[53]:= AccurateTiming[First@AbsoluteTiming[Pause[Random[]];],
TimeConstraint -> 20]
Out[53]= 0.51018
