Several different methods have been investigated in recent years aiming at computational complexity reduction and scaling of High Efficiency Video Coding (HEVC) software implementations. However, maintaining the encoding time per frame or Group of Pictures (GOP) below an adjustable upper-bound is still an open research issue. A solution for this problem is devised in this work based on a set of Pareto-efficient encoding configurations, identified through Rate-Distortion-Complexity analysis. The proposed method combines a medium-granularity encoding time control (MGTC) with a fine-granularity encoding time control (FGTC) to accurately limit the HEVC encoding time below a predefined target for each GOP. It is shown that the encoding time can be kept below a desired target for a wide range of encoding time reductions, e.g., up to 90% in comparison to the original encoder. The results also show that compression efficiency loss (BD-rate) varies from negligible (0.16%) to moderate (9.83%) in the extreme case of 90% computational complexity reduction.