This paper presents a novel adaptive-frequency Model Predictive Control (MPC) framework for bipedal locomotion over terrain with uneven stepping stones. In this framework, we allow the robot to have varied gait periods in order to achieve different step lengths to avoid terrain gaps while maintaining a constant linear velocity. In detail, adaptive-frequency MPC works with varied gait periods for bipedal periodic walking gait. We pair this adaptive-frequency MPC with a kino-dynamics trajectory optimization for optimal gait periods, center of mass (CoM) trajectory, and foot placements. Due to varied sampling frequencies in MPC, trajectory tracking performance is affected with MPC-only control when MPC frequency is low. We use whole-body control (WBC) along with adaptive-frequency MPC to track the optimal trajectories from the offline optimization framework to achieve dynamic walking over uneven stepping stones. In numerical validations, our adaptive-frequency MPC framework with optimization has shown advantages over fixed-frequency MPC. The proposed framework can control the bipedal robot to traverse through uneven stepping stone terrains with perturbed stone heights, widths, and shapes while maintaining an average speed of 1.5 m/s.