To understand the fate of the host phase for potassium subducted into the deep Earth’s interior, we have studied the high-pressure stability and elastic properties of KAlSi3O8 hollandite (K-hollandite) by means of the first-principles computation method. Based on experimental observations, the tetragonal K-hollandite I phase was found to undergo a ferroelastic second-order phase transition to the monoclinic K-hollandite II phase at 14.9 GPa. This K-hollandite II phase was mechanically stable up to 150 GPa (i.e., entirely in the Earth’s lower mantle), being consistent with previous studies. The Born’s elastic stability criteria indicate that the tetragonal mechanical instability occurs at similar pressure of 16.9 GPa with shear softening. This causes anomalous pressure dependence of the wave velocities across the instability. Taking a Clapeyron slope of 7 MPa/K and a temperature of 1800 K, the transition pressure becomes ~28 GPa corresponding to about 770 km depth, which would be seismologically detectable and could be comparable to seismic scatterers observed at the shallowest lower mantle. Next, we studied the solid-solution effect of sodium to K-hollandite, indicating that it is very limited on the phase stability, although the Na-end-member phase was found to be metastable. Elasticity demonstrates strong anisotropy around 15 GPa due to its ferroelastic nature.