The Electric Autonomous Dial-A-Ride Problem (E-ADARP) consists in scheduling a fleet of electric autonomous vehicles to provide ride-sharing services for customers that specify their origins and destinations. The E-ADARP differs from the classical DARP in two aspects: (i) a weighted-sum objective that minimizes both total travel time and total excess user ride time; (ii) the employment of electric autonomous vehicles and a partial recharging policy. This paper presents a highly-efficient labeling algorithm, which is integrated into the column generation (CG) approach to solve the E-ADARP. To handle (i), we introduce a fragment-based representation of paths. A novel approach is invoked to abstract fragments to arcs while ensuring excess-time optimality. We then construct a new graph that possesses all feasible routes of the original one by enumerating all feasible fragments and connecting them with depots and recharging stations in a feasible way. On the new graph, partial recharging (ii) is tackled exactly by tailored Resource Extension Functions (REFs). We apply strong dominance rules and constant-time feasibility checking to efficiently compute the shortest paths. These methods pave the way for an efficient labeling algorithm that ensures excess-time optimality in the extension of a partial path. In the computational experiments, 50 instances out of 84 are solved optimally at the root node without branching, and we identify 10 new optimal solutions. The Lagrangian lower bounds have an average gap of 0.31% to the best-found solutions, and we enhance 24 previously-reported lower bounds and provide 17 new lower bounds for large-scale instances with up to 8 vehicles and 96 requests.