Malloc recibe un argumento de tipo size_t, el valor máximo que puede alcanzar está definido con la macro SIZE_MAX (definida en stdint.h). Normalmente suele tener el valor de un unsigned long long (2^64-1).

El problema no está en malloc. El problema son estos dos:

- Estás pidiendo memoria de forma contigua es muy posible que tengas 1 gb libre de memoria ram, el problema esque la memoria libre estará "dispersa". Es muy díficil que te encuentres 1 gb de espacio libre contiguo. Se podría suplir esto usando listas o varios vectores.
- En una aplicación de 32 bits, la máxima memoria permitida es de 2GB (si la compilas en 64 bits llegarías a los 16 tb)

Pues efectivamente, era por saltase iteraciones... Y porque el if que he puesto sobraba  

Y no soy tan nazi con las llaves xD. Ahí son pocas sentencias y se ve bastante claro. Yo lo hubiera identado de otra forma:

#include <stdio.h>
#define COMPUESTO 0
 
const int MAX = 1000000;
 
void tacharMultiplos(char Tabla[],int i)
{
    int j;
 
    for (j = i; (i*j) <= MAX; j+=2)
        Tabla[j*i] = COMPUESTO;
}
 
void mostrarTabla(char Tabla[])
{
    int i = 3,cont=1;
 
    for (i = 3; i <= MAX; i+=2)
        if (Tabla[i] != COMPUESTO) cont++;
 
    printf("\ncont= %d\n",cont);
}
 
int main()
{
    // Generar Criba de erastotenes
 
    char Tabla[MAX+1]; // tabla booleana
    int i = 0;
 
    // valor inicial
 
    for (i = 3; i<= MAX; i++)   Tabla[i] = i;
    for (i = 3; i*i<=MAX; i+=2)   tacharMultiplos(Tabla,i);
 
    mostrarTabla(Tabla);
    return 0;
}