The way Revit phases work is your wall is drawn in the phase that the view is set to. Because your phase is new construction, your walls are being drawn in new construction. If you want your walls to start out in existing, then you have to draw them in a view with the phase set to "Existing". However, you can't use phase filters to identify items demolished in a later phase. Since filters don't work on phase created/demolished parameters you can't use those to identify them either. You could set up a custom filter to show new, demo and existing elements and use that instead, but it may be hard to read if you have a lot of new work and you'll still need to manually adjust each elements created phase.

Typically, I draw the existing area in views with the Phase set to "Existing" then I demolish elements in a view with the Phase set to "New Construction" and a phase filter of "Show Existing + New". I only use the demo plan to grab items that were demolished by mistake, and when I'm cleaning it up to be part of the drawing set.

I would advise using a view in the existing phase to draw existing elements. Particularly if I have a lot of elements to demolish I want the view I demolish in to be in the new construction phase, so I can speed work up by using the demo hammer

Because the view phase is New Construction, Revit is assigning its "Phase Created" property to that phase, which will not be visible due to your view Phase Filter (Show Previous + Demo).

To draw an existing wall that will be demo'd, you need to be in a view with the Phase set to "Existing". Then the "Phase Created" property will be Existing. Then it will show as Existing in your New Construction phase views. You can then change it's "Phase Demolished" property to New Construction as needed.

When working on a remodel project, the first thing I do is create working views with the phase set to "Existing". Then I build the existing model in its entirety before I start slicing & dicing it. I keep these views and create others for the remodel work.

(Or "what jmk said", just using different words. )

We actually use shared parameters for phasing and then set up filters, and create view templates.
It is essentially doing what the in built phasing of revit does however we have greater control over elements and what is visible or not in our views. Also it entirely avoids the problem of what your phase your view is set to when creating an element. Also we can simply run out a schedule showing the phases by element and element ID and change the phasing in one sweep rather than object by object.

I have found quite a lot of advantages doing it this way. I will say though that the decision to use shared parameters rather than the revit phasing was initially made because we are on a project involving many different companies. Each company needed their own phasing for internal coordination, but also another set for external coordination and this was the driving reason behind that strategy, but as it turns out I find it much easier to work with and would recommend that you trial it out instead of the revit phasing mechanics in built.

We actually have 4 parameters set up to deal with that
Internal Demo
Internal Creation
External Demo
External Creation

If it is a piece of existing construction we use the revit creation phase of "existing"