This behaviour can be expected because by using a kd-tree you do not take into account the mesh connectivity (edges between two vertices). It only considers the distance between points/vertices. So points/vertices that are "close" are merged, regardless if they are connected by an edge in your mesh.

Instead you should use a proper mesh decimation algorithm such as the quadric edge collapse algorithm. There is a version in PyMeshLab able to preserve textures, which might do the trick for you.