Memory is divided into two types: stack and heap. Memory can be allocated and deallocated from the help while a program is running. On Windows, the stack size is fixed, and each time that a variable is declared with fixed dimensions in your Fortran MEX program, it takes some of the stack memory. While this might not be a problem when you pass your MEX file a 1000 element array, when you pass it 1,000,000 elements, it will likely complain.
The trick is to move variable off the stack and onto the heap. The surest way of doing this is by using ALLOCATABLE or POINTER gateways (examples 2 and 3 in FAQ 4). Both of these features require an F9x compiler. If you are restricted to F77, then put the large variables in a COMMON block, which should also force them onto the heap.