Count the number of times a function runs
One-million in binary is equal to 11110100001001000000 (20 bits).  Thus, we cannot implement a simple counter for this.  

Instead, the max number we can represent with 16 bits is 1111111111111111 = 65,535.  Since the answer requires that we only need to approximate 1 million function runs, we could add one to the counter approximately once every 16 function runs, and know that the function has run about 1 million times when the counter reaches 1000000/16 = 62500.  

Below is the pseudocode of a potential solution, assuming that counter is a positive integer stored in 16 bits.  Also, this assumes that calls such as random(1,16) do not count towards memory as long as they are not stored in a variable.  Last, the random(x,y) function should give a random integer between x and y inclusive.

counter = 0;

function amIAttaBoutaMillionYet(){
    if(random(1,16)==16 &amp;&amp; counter&lt;62501){
        counter++;
    }
    if(counter==62500){
        return true;
    }
    return false;
}


UPDATE

Fixed function so that it won't show true after about 2 million+, 3 million+, etc.   function runs.  (thanks trinithis!)