Here is how I would tackle this.

First create an SQL Sequence

CREATE SEQUENCE [dbo].[RecordSeq]
    START WITH 1
    INCREMENT BY 1
    MINVALUE 1
;

Then Create a Table in SQL

CREATE TABLE RecordID (
    ID int NOT NULL IDENTITY,
    RecordNumber bigint NOT NULL,
    YearMonth date DEFAULT GETDATE() 
);

Finally, in a Workflow Custom Query activity, use the following

-- Variables
DECLARE @NextVal BIGINT
DECLARE @CurDate DATE
DECLARE @RetVal INT
-- Get New Record ID
SELECT @NextVal = NEXT VALUE FOR [dbo].[RecordSeq]
-- Get Date
SELECT @CurDate = GETDATE()
-- Check if table already had entries for the month
SELECT @RetVal = COUNT(*) FROM [dbo].[RecordID] WHERE LEFT(CONVERT(VARCHAR(10),YearMonth,112),6) = LEFT(CONVERT(VARCHAR(10),@CurDate,112),6)
IF (@RetVal > 0) -- Already has entries in the month
  BEGIN
    -- Create new record entry
    INSERT INTO [dbo].[RecordID] (RecordNumber) VALUES (@NextVal)
  END
ELSE
  BEGIN -- Does not have record entry for the month
    -- Reset the Sequence
    ALTER SEQUENCE [dbo].[RecordSeq]
    RESTART
    -- Get New Record ID
    SELECT @NextVal = NEXT VALUE FOR [dbo].[RecordSeq]
    -- Create new record entry
    INSERT INTO [dbo].[RecordID] (RecordNumber) VALUES (@NextVal)
  END
-- Get the record entry ID in needed format
SELECT RIGHT(LEFT(CONVERT(VARCHAR(6), YearMonth, 112),6),2) + LEFT(CONVERT(VARCHAR(4),YearMonth,112),4) + RIGHT(REPLICATE('0',3) + CONVERT(VARCHAR(4),RecordNumber,4),4) AS RecID
FROM [dbo].[RecordID]
WHERE [YearMonth] = @CurDate AND [RecordNumber] = @NextVal;