Separate between logical tiles (that store properties like the tile type) and graphical sprites (which are only used to render the tiles). Then, you don't need a sprite for each tile, and you can also create sprites on the fly instead of storing them all the time.
By the way, 400 * 600 * sizeof(sf::Sprite) is about 45MB. I don't think you need that much memory only for the sprites.