You can find a YouTube playlist here with many of the songs suggested below.
Gathering
God’s covenant has been a running theme throughout the Old Testament passages in Lent and this would work well as an opening theme today as well as we look towards the new covenant and the hope that comes with that. I give you my heart (CCLI), Waiting here for you (CCLI) and All my hope on God is founded (CH 192 / MP 16) are good gathering songs on this theme while also picking up on the image of the heart from v33. Every promise (CCLI / Getty) and Jesus, lover of my soul (CH 490 / MP 372) are more explicit about the new covenant bringing about pardon for our sin. Great is thy faithfulness (CH 153 / MP 200) and Let his praise be on our lips (Satellite) are more general options here while Meekness and majesty (CH 356 / MP 465) would set the scene for looking towards Easter.
For congregations who don’t sing a full setting of the mass every week, one good way to distinguish Lent as a season is to sing a Kyrie as a response to the prayer of confession. This may be unfamiliar liturgically in some traditions but fits the readings well as Psalm 51 sets the tone for the season. CH4 offers three contrasting options which are all easy to pick up with James MacMillan’s Lord, have mercy (CH 648), the Ukranian Orthodox Kyrie eleison (CH 776) and John Bell’s call and response Kyrie eleison (CH 777). This is also a great chance to learn a song from other parts of the world and Khudaayaa, raeham kar (WGRG / PFAS 51G) Ya Tuhanke (WGRG) are from Pakistan and Indonesia, places we rarely sing songs from. Both can be sung in English but try to imitate the slides on the recording of the first which is an important part of the style. Kyrie eleison, have mercy (MP 1321 / Townend) is more suited to worship bands and can be used either just as a chorus or else the verses can help set the context while Lord have mercy (Resound) would suit a variety of instrumentations. Create in me a clean heart O God (PFAS 51F) isn’t a Kyrie but is also from Psalm 51 and could also be an appropriate response to prayers of confession and Hear the song of our lament (Resound) would be an interesting song to use if you wanted to intentionally bring a whole of creation perspective.
Word
All of the Kyries suggested above could also be used for a responsorial reading of Psalm 51. If you would like to sing a full metrical setting then consider either O God, be gracious to me in your love (CH 40) or God be merciful to me (Grace). There are also a number of songs which pick up particularly on v10 such as Create in me a clean heart O God (PFAS 51F) mentioned above, Create in me (CCLI) and Change my heart, O God (PFAS 51A / CCLI).
Response
Our God has made his covenant new (Jubilate) is a direct response to the Old Testament reading, exploring what it means for us both personally and corporately. Help us, O Lord, to learn (STF 501) and My heart is filled with thankfulness (MP 1209 / CCLI) both reference God’s laws being written on our hearts while The Father’s song (MP 1063 / CCLI) also does this in a more poetic way.
The reference in the Epistle to Jesus as our great High Priest is picked up in a lot of songs linked more to the Ascension such as Before the throne of God above (CH 466 / MP 975), Join all the glorious names (CH 460 / MP 392) and The Lord ascendeth up on high (CH 440). High Priest (CCLI) could be a useful contemporary option although it is probably more suited to a soloist than a congregation.
The chorus and first two verses of Unless a single grain of wheat (CH 347) are lifted directly from vv.24-26 of the Gospel reading. The chorus is very easy for a congregation to pick up although the verses may be better sung by a cantor or choir. Other songs which use the imagery of a seed rising to life are the beautiful Japanese chant Hitotsubu no / When a grain of wheat (MV 125 / GP3 178), Tree of life and awesome mystery (CH 401) and In our lives plant seeds of hope (CH 349) which puts these verses into the wider context of other stories from the Gospels about seeds. Lifted high on your cross (CH 386) is inspired by v.32 and the folk melody is easy to pick up and makes for a catchy earworm while Worthy is the lamb (MP 1109 / CCLI) could be another option to link with this.
Sending
The Gospel has a call to follow and we can link this with the wider themes of God’s new covenant and Jesus’ sacrifice for us. O Jesus, I have promised (CH 644 / MP 501) and I, the Lord of sea and sky (CH 251) both have that explicit commitment to follow Jesus in them while I stand amazed (How marvellous) (CCLI) and O love, how deep, how broad, how high (CH 354) speak more of Jesus bearing our sins. In Christ alone (MP 1072 / CCLI / Getty), Cornerstone (CCLI) and Living hope (CCLI) would give a focus on the hope we have because of God’ covenant with us as we approach Easter.