Turn down the difficulty, or just mix your low attacks and throws in with high percentage combos.

this is how I beat him:
after many tries i couldnt beat him.
so i relaxed myself by playing konquest and finding random crap.
finally when i had the nerve to challenge him again, i psyched myself and said i wont win.
i played Petey Pablo's song and thats how i kind of got distracted cuz i was just pressing squarex3 and throw and randow crap that i came up with.
so out of luck i beat him 3 times in a row!
so i suggest that you get some costumes and get stuff that you missed out of to relax and chill. then know shujinko's basic moves, and play a very distracting song and sing along while pressing:
square, square, triangle >>triangle...then R1...
be happy now cuz when you have to beat scorpion for shujinko's spear move its REALLY HARD!!
for that use Kobra!
see i helped twice in a row!

Well I beat Him On The hardest Difficulty I Guess I Am The True Master Of Konquest!

The easiest way i found is feep quiting the match till you get milenna, alternate the kick from above, and throm, dont stop or hesitate, and you can beat him. hope this helps.

It took me a while too , but the way i pulled it off was to use your sword and just do the uppercut with it, but its gonna take some practice to learn just the right time to do it, so he wont be able to block it or miss him.