With the availability of internet, social media, etc., the interconnectedness of people within most societies has increased tremendously over the past decades. Across the same timespan, an increasing level of fragmentation of society into small groups has been observed. With a simple model of societies, in which the dynamics of opinion formation is integrated with social balance, we show that these two phenomena might be tightly related. We identify a critical level of interconnectedness, above which society fragments into subcommunities that are internally cohesive and hostile towards other groups. This critical density necessarily arises from the underlying mathematical structure of a phase transition known from the theory of spin glasses.