Take a look at this page, it lists the maximum sizes: Max sizes
It looks to be on the order of a few hundred million. Note that the matrix you're trying to create here is: 10e6 * 10e6 = 10e12 elements. This is many orders of magnitude greater than the max sizes provided and you also do not have that much RAM on your system.
My suggestion is to look into a different algorithm for what you are trying to accomplish.
To find out the real maximum array size (Windows only), use the command user = memory. user.maxPossibleArrayBytes shows how many bytes of contiguous RAM are free. Divide that by the number of bytes per element of your array (8 for doubles) and you know the max number of elements you can preallocate.
Note that as woodchips said, Matlab may have to copy your array (if you pass by value to a subfunction, for example). In my experience 75% of the max possible array is usually available multiple times.
My original answer returned the maximum element of the cell. Now including your comments the right code:
knedlsepp basically got it. Minor improvement in performance:
[a(:,1),a(:,2)]=cellfun(@size,A);
max(a)
I guess you are looking for:
max(cell2mat(cellfun(@size,A(:),'uni',0)),[],1)