You have to sum up the size for the palette and the sizes for each mipmap level. E.g. for a 8x4 texture in PALETTE4_RGB8 format:
Palette: 16 * 24 / 8 = 48
Level 0: 8 * 4 * 4 / 8 = 16
Level 1: 4 * 2 * 4 / 8 = 4
Level 2: 2 * 1 * 4 / 8 = 1
Level 3: 1 * 1 * 4 / 8 = 1 (rounded up)
Total size: 48 + 16 + 4 + 1 + 1 = 70 bytes

In addition, the level parameter to glCompressedTexImage2D needs to be (1 - number of levels) for paletted textures, so for this example it would be:
glCompressedTexImage2D(GL_TEXTURE_2D, -3, GL_PALETTE4_RGB8_OES, 8, 4, 0, 70, data);