The juxtaposition of קדר and הלך occurs six times in תנ”ך, once with the unusual, and perhaps unrelated form קדרנית.

מלאכי ג, יד
אֲמַרְתֶּ֕ם שָׁ֖וְא עֲבֹ֣ד אֱלֹהִ֑ים וּמַה־בֶּ֗צַע כִּ֤י שָׁמַ֨רְנוּ֙ מִשְׁמַרְתּ֔וֹ וְכִ֤י הָלַ֨כְנוּ֙ קְדֹ֣רַנִּ֔ית מִפְּנֵ֖י יְהוָ֥ה צְבָאֽוֹת׃

תהלים לה, יד
כְּרֵֽעַ־כְּאָ֣ח לִ֭י הִתְהַלָּ֑כְתִּי כַּאֲבֶל־אֵ֝֗ם קֹדֵ֥ר שַׁחֽוֹתִי׃

תהלים לח, ז
נַעֲוֵ֣יתִי שַׁחֹ֣תִי עַד־מְאֹ֑ד כׇּל־הַ֝יּ֗וֹם קֹדֵ֥ר הִלָּֽכְתִּי׃

תהלים מב, י
אוֹמְרָ֤ה ׀ לְאֵ֥ל סַלְעִי֮ לָמָ֪ה שְׁכַ֫חְתָּ֥נִי לָֽמָּה־קֹדֵ֥ר אֵלֵ֗ךְ בְּלַ֣חַץ אוֹיֵֽב׃

תהלים מג, ב
כִּֽי־אַתָּ֤ה ׀ אֱלֹהֵ֣י מָֽעוּזִּי֮ לָמָ֪ה זְנַ֫חְתָּ֥נִי לָֽמָּה־קֹדֵ֥ר אֶתְהַלֵּ֗ךְ בְּלַ֣חַץ אוֹיֵֽב׃

איוב ל, כח
קֹדֵ֣ר הִ֭לַּכְתִּי בְּלֹ֣א חַמָּ֑ה קַ֖מְתִּי בַקָּהָ֣ל אֲשַׁוֵּֽעַ׃

The root קדר means to become dark, to be in mourning garb, or to be in mourning (HALOT).  On Malachi 3:14, Tawil points out the parallelism between כי שמרנו משמרתו and כי הלכנו קדרנית, and suggests that it should be from קדד with a ר and ד interchange, meaning “to walked bowed”, to serve, so be prostrate.  He then suggests that the expression understood that way is a semantic equivalent to Isaiah 60:14 וְהָלְכ֨וּ אֵלַ֤יִךְ שְׁח֨וֹחַ֙ בְּנֵ֣י מְעַנַּ֔יִךְ וְהִֽשְׁתַּחֲו֛וּ עַל־כַּפּ֥וֹת רַגְלַ֖יִךְ כׇּל־מְנַֽאֲצָ֑יִךְ וְקָ֤רְאוּ לָךְ֙ עִ֣יר יְהוָ֔ה צִיּ֖וֹן קְד֥וֹשׁ יִשְׂרָאֵֽל׃

The juxtaposition of הלך and קדר in the four verses in Psalms supports this reading.  Two of the verses explicitly use the verb שחותי.

However, Psalms 35:14 and Job 30:28 both suggest not service but mourning, and the verse in Job suggests a connection to darkness, קדר הלכתי בלא חמה.