Wal segment still exists on master, but logs on slave and master say it's been removed
It is as dezso alluded to in the comment. 
The reason you get the error is because the WAL has already been archived. 

You can configure how many segments to store on the master with the wal_keep_segments configuration. You should set it to at least the amount of WAL's created during the base backup (and some extra as buffer).

Since the standby doesn't connect to the replication slot until it is ready to use it (which is after the base backup is finished), it means that the slot has not been activated yet and therefore is not storing the old WAL's.