It is a legal move because the building of a tower and removal of a follower are part of the same turn.
In the Tower you do not have to lay a tower tile to be able to construct a tower, all that is required is a tile with tower foundations to have already been played in a previous turn. You can add a tower piece to
any tile that shows tower foundations or has a tower 'under construction', (provided it is not 'guarded'), regardless of who laid the tile, and remove a follower in the towers 'catchment' area in the same turn. Hope this answers your question.