Lt. Nyota Uhura is a communications specialist, with a talent for languages by ear. This extended to her analysis of Krall, as she is the only one he speaks to at length aside from Kirk. Specifically:
The Federation has pushed the frontier for centuries.
But now enough.
This is where it begins, Lieutenant.
This is where the frontier, pushes back.
And in the video log when Uhura analysis it, there is a bit where Edison, back towards the camera, says:
...expand the frontier...
rewind
...expand the frontier...
rewind, slow down
...expand the frontier...
Nyota plays back the video multiple times, slowing it down.
She also sees first hand Krall absorbing the life forces of two human crew members, and his skin and voice changing accordingly. Both become less bumpy, grungy, more smooth, more human.
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. Right after the rewinds:
Uhura: It's him. Scotty, I need you to link to Franklin database.
Find out what you can about Balthazar Edison.
Scott: What?! The Captain of the Franklin?
Uhura: Yes.
Scott: He is long dead.
Uhura: No he is not. I do not know how, but Edison is Krall.