Slightly expanding my comment. It is a partial answer, explaining most but not all of the observed timing increase. First I show some representative timings. Note that I use 2^16-1 and 2^21-1 below, for reasons that will be explained.
AbsoluteTiming[RandomInteger[2^16 - 1, 100000000];]
AbsoluteTiming[RandomInteger[2^21 - 1, 100000000];]
(* Out[37]= {1.0384, Null}
Out[38]= {1.27375, Null} *)
AbsoluteTiming[RandomInteger[2^15, 100000000];]
AbsoluteTiming[RandomInteger[2^20, 100000000];]
(* Out[39]= {2.44224, Null}
Out[40]= {2.91487, Null} *)
Generating random integers between 0 and 2^15 means creating randoms, uniformly distributed, almost all of which are 16 or fewer bits (except we have to allow for 2^15, which requires 16 bits to represent in binary). All underlying methods in the Mathematica kernel generate some batch of bits at a time. For this case, 16 get strung together. The examples above that generate between 0 and either 2^16-1 or 2^15 both use sets of 16 bits. The latter case will discard all values larger than 2^15, which is to say, around half the time a generated value gets tossed. This accounts for a factor of 2 or so in the speed differences. The total differences above are more like a factor of 2.4, so this is clearly not the full explanation.
If we work with 2^16 - 2 as upper bound the timing gets slightly slower than for 2^16-1. My guess, not looking at the code, is that the exact power-of-2 bits special case is fast because no check for exclusion is performed. If we look at cases where it must be performed but essentially never discards, the respective timing ratios get closer to 2.
AbsoluteTiming[RandomInteger[2^16 - 2, 100000000];]
AbsoluteTiming[RandomInteger[2^21 - 2, 100000000];]
(* Out[41]= {1.18563, Null}
Out[42]= {1.32423, Null} *)
The ratios are still above 2. My guess at this point is that there is some modest inefficiency in the way new sets are generated and merged to cover for the values discarded. Specifically, it might be the case that exactly the number discarded get generated, causing, in the worst case, another half or so tof the new set to be tossed, so repetitions get us into a log(n) loop where n is the number of values being generated. It could be faster to generate roughly twice as many as needed to account for the approximate size of the set that will be discarded. All this is speculation; I last had dealings with that code I think in the 1990's. In particular I do not recall how the generate-and-discard process decided on how many to generate at each step. So my speculation might be on target if it is generating exactly the number needed, or if it is generating some fixed fraction beyond the estimated number required to fill the customer's order, so to speak.
RepeatedTiming[RandomInteger[{0, 2^15}, 100000000];]is slower, butRepeatedTiming[RandomInteger[{0, 2^15 - 1}, 100000000];]is fast... It perhaps has something to do with the data types selected internally by the RNG depending on the range over which the numbers are requested, but I don't know for sure. $\endgroup$