First, your question contains a typo, you mean 32,768 (2^15) not 37,768.
The PIC in question has a 16-bit instruction word.
The flash memory size is specified as 64K (65536) bytes. With two bytes per word, that is space for 32768 simple instructions.
Many processors, apparently including this one, offer instructions of varying length - more complex instructions may include things like immediate operands or memory addresses. These take more bits to encode, and so are longer than the "single-word" instructions.
The data sheet is thus giving you a best case. Depending on the compiler or hand coding strategy, actual code might have varying average instruction length, so it is harder to say how many typical instructions could fit in flash. Even if it's possible to write a program using all single-word instructions, on a machine designed to support them it may well be more efficient to use some multi-word ones, especially if that avoids needing to go do another fetch of a constant from data memory.