I was told that the effect of pressure on an NaCl type structure would make the atoms come closer and therefore change the type to CsCl type making Z (no of atoms per unit cell) go down, hence density decreases. Won't the added pressure increase the density of the structure? Am I wrong in saying so?
Two things to consider:
Even though the sodium chloride crystal structure is face-centered cubic, it is not 12-coordinate. Face-centered cubic refers to the lattice formed by periodically equivalent atoms or ions, which in sodium chloride is commonly taken to be the chloride ions. But the chloride ions are not directly coordinated to each other; they are instead coordinated to the intervening sodium ions and that makes them only six-coordinate. Switching to what is usually the caesium chloride structure increases the coordination number of each chloride ion (and each sodium ion) from six to eight, which is a normal effect of increasing pressure.
Placing fewer atoms in a unit cell means lower density if the unit cell remains the same size. But when the sodium chloride switches structure, it not only goes from eight atoms/ions in the normal unit cell down to two in the high-pressure cell. The high-pressure cell is also much smaller than the normal one, a condition promoted by the increased coordination number noted in (1). The net result is that the high-pressure unit cell is less than one-fourth the volume of the normal one, so the density will be higher even with only two ions in the high-pressure unit cell.
You've gotten a good answer from Oscar explaining the atomic details of what's actually happening.
More broadly however, it is important to note that, irrespective of the atomic details, it's physically impossible for an isotropic substance to decrease in density when the pressure increases.* That's because it would enable a violation of the first law of thermodynamics (conservation of energy). If a substance did decrease in density when you increased the pressure, you could use it to build a perpetual motion machine of the first kind.
To illustrate this, assume you did have such a substance. Imagine you submersed it in an incompressible fluid, and put the substance + fluid in a cylinder with a moveable piston at the top. Now put a heavy mass on top of the piston, which increases the pressure on the substance, causing it to expand (if its density decreases, its volume must increase). Thus the piston head would rise, and the heavy mass would be lifted. Now move the mass laterally, and let it descend to its original height. Couple it to something (e.g., an electrical generator) so that the mass does work as it descends. Since you've moved the mass off of the piston, it has also descended back its original height. So now you can move the mass laterally back to the piston head. It rises again.
Thus by moving the mass back and forth you'd be creating energy for free. Specifically, since you keep returning your piston system back to its original state, $\Delta E$ for that is zero. However, each time you move the mass to the other system, it's able to do work as it descends.
*Unless you're Lisa Simpson: https://www.youtube.com/watch?v=4FN_DGxZ2dM