#Pyth, 11 bytes
WOyG~ZtOT)Z
Note: this program will probably crash with a memory error on any real computer. To test it, try replacing G with a shorter string, such as in this code, which generates numbers averaging around 28000:
pyth -c 'WOy"abcdefghijklm"~ZtOUT)Z'
This code loops, adding a random number from -1 to 8 to Z, with a 2^-26 probability of exiting the loop on each repetition. The 2^-26 probability is attained by selecting a random element (O) of the set of all subsets (y) of the alphabet (G).
Technical details & justification:
The probability 2^-26 is derived from two facts: y, when called on sequences, is the power-set function, an constructs the list of all subsets of the input. Since the input, G, is 26 characters long, this power-set, yG has 2^26 entries. OyG selects a random element from those 2^26 entries. Exactly one of those entries, the empty string, will evaluate as falsy when passed to W, the while loop. Therefore, there is a 2^-26 probability of exiting the loop each time.
In any fixed number of loop cycles K, the probability of getting the number K3.5 + m and getting K3.5 - m are equal, because each sequences of addends that achieves one total can be inverted, -1 -> 8, 0 -> 7, etc., to achieve the other. Additionally, numbers closer to K*3.5 are clearly more likely than numbers farther away. Thus, if K > 2000000/3.5 = 571428.5 the probability of getting a number over 1000000 is greater than 75%, because some of the results above that number can be put into a one-to-one correspondence with all of the results below that number, and the upper less-than-half, can be put into a one-to-one correspondence with those under 1000000. The probability of getting at least 571429 loops is (1-2^-26)^571429, which is no less than (1-2^-26 * 571429), the expected number of times leaving the loop over the first 571429 tries, which is 99.1%. Thus, on 99.1% or more of trials, there is a 75% or more chance of getting at least 1000000, so there is more than a 50% chance of getting over 1000000.
This code relies on a behavior of O where a bug was accidentally introduced 3 days ago and was fixed today. It should work on any version of Pyth 3 from before Dec 22nd, or after today. The following code is equivalent, and has always worked:
WOyG~ZtOUT)Z