In the video below Ryan Leach demonstrates a quick and easy method to compose a counter melody.
Starting with a main melody, chord progression and bass line, to compose your counter melody do the following:
1. Find missing chord tones.
Examine the melody and bass line to find any missing chord tones from each chord. If the current chord is a C (C E G), and the melody is playing a G (and then perhaps other non chord tones), and the bass is playing a C, the missing note is E. Use E as your counter melody note. Use a whole note or other long note for now. If the melody is playing multiple chord tones (perhaps both E and G) choose a chord tone to double. From the rules of harmony, it seems that the root (C) of the chord or the fifth (G) are the ones recommended to be doubled.
When adding a missing chord tone (or doubling a chord tone), another thing to consider is which of the chord tones is closest to the previous harmony note. For example, if you’ve chosen a G harmony note to accompany a C from the previous bar, and you now need to fill in harmony for an F chord and there are two missing notes from that chord in the current bar, say for example the C and the A are missing from the F chord, a good choice would be to use A as the harmony note since it is closest to the previous G harmony note from the previous bar.
2. Add rhythm
Having worked out what starting notes to play for the counter melody, now consider the rhythm. The idea is to have the counter melody resting or holding a note while the main melody is busy, and have the counter melody busy while the main melody is holding a note or resting. Using a missing chord tone for the counter melody in step 1, was a starting point. To add rhythm to the counter melody, other notes from the key can be used to move form one chord tone to the next.
The above two steps (and adding a second harmony part by repeating those two steps) are demonstrated in greater detail in the following video: