Question: how did uhura know who krall was?
Answer: Between changing the pitch of the Video, and Krall's changing voice, and the specific keyword of Frontier, it clicked in her head. She still didn't know exactly how or why, but she knew Krall is Edison from watching the video.