Is it correct to say je vais parler avec lui?
It is. However the meaning can be slightly different.
Je vais lui parler.
I'm going to speak to him, tell him something.
Je vais parler avec lui.
We'll have a chat.
Thanks for taking the time to reply